网上说是容斥，说简单点就是补集转化，再简单点就是总方案-不合法方案
我们枚举和联通块中编号最小的点联通的点集
联通块为i，枚举的点集为j，首先j必须是联通的，然后j和i^j不能有连边，然后i^j内部是随便连的
这样枚举保证不重不漏
令F[i]表示点集为i必须联通的方案
G[i]表示点集为i不保证联通的方案
核心思想是枚举和编号最小点联通的块
#include<cstdio>
using namespace std;
const int mod=1e9+7;
int c[25][25],stack[25],F[70005],G[70005],ID[70005];
int lowbit(int x){
return x&(-x);
}
int main(){
int n;
scanf("%d",&n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
scanf("%d",&c[i][j]);
G[0]=1;
for (int i=0; i<n; i++) ID[1<<i]=i;
for (int i=1; i<(1<<n); i++){
int top=0;
for (int j=i; j; j-=lowbit(j)) stack[++top]=ID[lowbit(j)];
G[i]=G[i-lowbit(i)];
for (int j=2; j<=top; j++) G[i]=1ll*G[i]*(c[stack[1]][stack[j]]+1)%mod;
}
for (int i=1; i<(1<<n); i++){
F[i]=G[i];
for (int j=(i-1)&i; j; j=(j-1)&i)
if (j&lowbit(i)){
F[i]-=1ll*F[j]*G[i^j]%mod;
(F[i]+=mod)%=mod;
}
}
printf("%d\n",F[(1<<n)-1]);
return 0;
}
原文：https://www.cnblogs.com/silenty/p/9866602.html