BZOJ2560:串珠子 状压dp

思路:

令\(f[S]\)表示集合S形成连通图的方案数,\(g[s]\)表示集合S内部任意连边的方案数.

显然:

\[g[S]=\prod_{i,j\in{S},i<j}c_{i,j}+1\]

这个我们可以在\(O(2^n{n^2})\)的复杂度内算出来.

接下来考虑计算\(f[S]\).

我们用总数减去不连通的图的个数.

假设\(x\in{S}\),我们不妨枚举所有\(S\)的真子集\(S'\),其中\(S'\)就代表包含\(x\)的一个连通块,\(S-S'\)均与\(x\)不连通.

那么\(f[S']\)我们已经算过了,剩下的\(S-S'\)就利用我们之前预处理的随意连边的\(g\)数组.

于是我们得到转移:

\[f[S]=\sum_{S'\subset{S},x\in{S'}}f[S']g[S-S']\]

这个过程是\(O(3^n)\).

然后我们就在\(O(2^n{n^2}+3^n)\)的时间内解决了这题.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
#define N 16
 
int f[1<<N],g[1<<N],h[1<<N],c[N][N];
static const int mod=(1e9)+7;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
 
#define p(S,x) (((S)>>(x))&1)
 
int main(){
    int n;scanf("%d",&n);register int i,j,k;
    for(i=0;i<n;++i)for(j=0;j<n;++j)scanf("%d",&c[i][j]);
    for(i=0;i<n;++i)f[1<<i]=g[1<<i]=1;
    for(i=1;i<(1<<n);++i)h[i]=h[i^(i&-i)]+1;
    for(i=1;i<(1<<n);++i){
        if(h[i]==1)continue;
        else{
            g[i]=1;
            for(j=0;j<n;++j)for(k=j+1;k<n;++k)if(p(i,j)&&p(i,k))
                g[i]=(LL)g[i]*(c[j][k]+1)%mod;
            int ins;
            for(j=0;j<n;++j)if(p(i,j)){ins=j;break;}
            for(int mas=(i-1)&i;mas;mas=(mas-1)&i)if(p(mas,ins))
                inc(f[i],(LL)f[mas]*g[i^mas]%mod);
            f[i]=(g[i]>=f[i])?g[i]-f[i]:g[i]+mod-f[i];
        }
    }
    printf("%d",f[(1<<n)-1]);
    return 0;
}