题意：
铭铭有n个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连接成一个整体。
现在已知所有珠子互不相同，用整数1到n编号。对于第i个珠子和第j个珠子，可以选择不用绳子连接，或者在ci,j根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。
铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大，因此只需输出答案对1000000007取模的结果。
题解：
看到计数考虑容斥！而且在n怎么小的情况下。
假如不需要连通那么就是到sb题。
预处理 g[S] 表示选点状态S时的方案数。
然后容斥，将点分成与某个定点相连，其它随便的两部分。
枚举子集，所以 f[S]=g[S]−∑g[j]∗f[Sxorj]
code：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#define LL long longusing namespace std;const LL mod=1000000007;LL n,g[66000],f[66000];LL c[20][20];void pre(LL S){g[S]=1;for(LL i=1;i<=n;i++)if((1<<(i-1))&S)for(LL j=i+1;j<=n;j++)if((1<<(j-1))&S) (g[S]*=(c[i][j]+1))%=mod;}int main(){scanf("%lld",&n);for(LL i=1;i<=n;i++)for(LL j=1;j<=n;j++) scanf("%lld",&c[i][j]);for(LL i=0;i<(1<<n);i++) pre(i);for(LL S=0;S<(1<<n);S++){f[S]=g[S];LL i=S^(S&-S);for (LL j=i;j;j=(j-1)&i) f[S]=(f[S]-g[j]*f[S^j]%mod+mod)%mod;}printf("%lld",(f[(1<<n)-1])%mod);}
如果觉得《bzoj 2560: 串珠子》对你有帮助，请点赞、收藏，并留下你的观点哦！
