Description

定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与

G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.

现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异

或为一个连通图?

Solution

连通性的题目我们可以容斥,这题的容斥系数是斯特林数,大致就是个斯特林反演.

设 \(f[i]\) 表示连通块个数恰好为 \(i\) 的方案数 , \(g[i]\) 表示至少为 \(i\) 的方案数.

那么 \(f[i]=\sum_{j=i}^{n}(-1)^{j-i}*g[j]*s(n,m)\).

\(g[i]=\sum_{j=i}^{n}S(j,i)*f[j]\)

其中 \(S(n,m)\) 为第二类斯特林数 , \(s(n,m)\) 为第一类斯特林数.

我们要求的是 \(f[1]\) , 也就是 \(f[1]=\sum_{i=1}^{n}(-1)^{i-1}*s(i,1)*g[i]\)

\(s(i,1)=(i-1)!\) , 于是有\(f[1]=\sum_{i=1}^{n}(-1)^{i-1}*(i-1)!*g[i]\).

现在就是要求 \(g[i]\) , 我们可以 \(O(bell(n))\) 的枚举划分 , 再考虑方案数.

首先属于两个集合的边一定不能出现 , 而在同一集合的随意.

于是可以列出边和图的对应方程 , 现在就是要求有多少张图是自由元.

用高斯消元或者线性基求出来就行了.

#include
    
     using namespace std;typedef long long ll;const int N=110;bitset
     
      a[65],b[65],t;int n,s,m,c[N],Fac[N];char T[N];ll ans=0,bin[N];inline void solve(int S){    int cnt=0,o=0;    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++)            if(c[i]!=c[j])t.set(cnt++);            else t.reset(cnt++);    for(int i=1;i<=s;i++)a[i]=b[i]&t;    for(int i=1,k=0;i<=s && k
      
       >s;  for(int i=1;i<=s;i++){      scanf("%s",T);m=strlen(T);      for(int j=0;j