一般图完美匹配计数
Imerance1018 · · 算法·理论
省流:时空复杂度
考虑往匹配方案中添加
由于我们需要钦定环经过这些新边,相当于有用的点只有
我们令
详细说一下怎么求
::::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;
}
::::::