一般图完美匹配计数

· · 算法·理论

省流:时空复杂度 O(2^{\frac{n}{2}}n^3)。

考虑往匹配方案中添加 (1,2),(3,4),\cdots,(n-1,n) 这 \frac{n}{2} 条新边,则每种匹配方案一定是若干个互不相交的环,这样就转化成了环计数问题。

由于我们需要钦定环经过这些新边,相当于有用的点只有 \frac{n}{2} 个,因此可以直接状压 DP 求出集合 S 拼出单个环的方案数 f_S,这一部分是瓶颈。

我们令 F(S)=\sum{f_Sx^S},则答案的集合幂级数 G(S)=\exp(F(S))。(子集卷积意义下)直接求 \exp 即可。

详细说一下怎么求 \exp:考虑子集卷积相当于多开一维记录 \operatorname{popcount},即相当于对 S 一维做或卷积,|S| 一维做普通卷积。由于 fwt 的性质,我们先在 |S| 维上做 fwt,然后在 |S| 维上暴力 \exp,最后逆 fwt 回来即可。

::::info[Code]

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define pnt(x) __builtin_popcount(x)
using namespace std;
const int mod=1e9+7;
void add(int &x,int y){x+=y; if(x>=mod) x-=mod;}
int inv[31];
int n,m,k;
bool is[30][30];
int f[1<<15],g[16][1<<15],h[16][1<<15];

void fwt(int *vl,int v)
{
    for(int i=0;i<k;i++)
        for(int j=0;j+(1<<(i+1))-1<(1<<k);j+=(1<<(i+1)))
            rep(t,j,j+(1<<i)-1)
                if(v==1) add(vl[t+(1<<i)],vl[t]);
                else add(vl[t+(1<<i)],mod-vl[t]);
}
int dp[30][1<<15];
signed main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    inv[1]=1;
    rep(i,2,30) inv[i]=(mod-1ll*inv[mod%i]*(mod/i)%mod);
    cin>>n>>m;
    rep(i,1,m)
    {
        int u,v; cin>>u>>v;
        u--,v--;
        is[u][v]=is[v][u]=1;
    }
    if(n&1) return cout<<"0\n",0;
    k=n>>1;
    rep(st,0,n-1)
    {
        rep(i,0,n-1) rep(S,0,(1<<k)-1) dp[i][S]=0;
        dp[st][1<<(st>>1)]=1;
        rep(S,0,(1<<k)-1)
            rep(i,st,n-1)
            {
                int cur=dp[i][S];
                if(!cur) continue;
                if(is[i^1][st]) add(f[S],cur);
                rep(j,(st>>1)+1,k-1)
                    if(!((S>>j)&1))
                    {
                        int cx=j<<1;
                        if(is[i^1][cx]) add(dp[cx][S|(1<<j)],cur);
                        if(is[i^1][cx^1]) add(dp[cx^1][S|(1<<j)],cur);
                    }
            }
    }
    rep(i,0,(1<<k)-1) g[pnt(i)][i]=f[i]*inv[2]%mod;
    rep(i,0,k) fwt(g[i],1);
    rep(S,0,(1<<k)-1)
    {
        h[0][S]=1;
        rep(i,1,k)
        {
            rep(j,1,i) add(h[i][S],j*g[j][S]%mod*h[i-j][S]%mod);
            h[i][S]=h[i][S]*inv[i]%mod;
        }
    }
    rep(i,0,k) fwt(h[i],-1);
    cout<<h[k][(1<<k)-1]<<"\n";
    return 0;
}

::::::