题目大意
铭铭有(n)个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连接成一个整体。
现在已知所有珠子互不相同，用整数(1)到(n)编号。对于第(i)个珠子和第(j)个珠子，可以选择不用绳子连接，或者在(c_{i,j})根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。
铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大，因此只需输出答案对(1000000007)取模的结果。
题目分析
考场上想到求补集，但依然毫无思路啊。
记(g[S])表示点集为(S)，连通状态任意的方案数，(f[S])表示点集为(S)且都与(1)号节点连通的方案数。那么状态转移方程为:
(f[S]=g[S]-sumlimits_{Gsubsetneqq S}f[G] imes g[Goplus S])。
解释一下方程，即:枚举点集为(S)的真子集(G)与(1)号节点连通，(G oplus S)与(1)号节点不连通(其内部连通状态任意)，这样的方案数和即为所有点集为(S)与(1)号节点不连通的方案数(sum)，补集思想转换一下(g[S]-sum)即为(f[S])。
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,c[16][16],f[1<<16],g[1<<16],Lg[1<<16];
int lowbit(int x){return x&-x;}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&c[i][j]);
for(int i=0;i<n;i++)Lg[1<<i]=i;
for(int i=1;i<(1<<n);i++){
static int st[17];
int top=0;
for(int j=i;j;j-=lowbit(j))st[++top]=Lg[lowbit(j)];
int ans=1;
for(int j=1;j<top;j++)
for(int k=j+1;k<=top;k++)
ans=1ll*ans*(c[st[j]][st[k]]+1)%mod;
g[i]=ans;
}
for(int i=1;i<(1<<n);i++){
int ans=0;
for(int s=(i-1)&i;s;s=(s-1)&i){
if((i^s)&1)ans=(ans+1ll*f[i^s]*g[s])%mod;
}
f[i]=(g[i]-ans)%mod;
}
cout<<(f[(1<<n)-1]+mod)%mod<<"
";
}