题目描述
定义两个图\(G_1\)与\(G_2\)的异或图为一个图\(G\)，其中图\(G\)的每条边在\(G_1\)与\(G_2\)中出现次数和为\(1\)。
给你\(m\)个图，问你这\(m\)个图组成的集合有多少个子集的异或图为一个连通图。
\(n\leq 10,m\leq 60\)
题解
考虑枚举图的子集划分，让被划分到不同子集的点之间没有连边，而在同一个子集里面的点可以连通，可以不连通。
可以用高斯消元（线性基）得到满足条件的图的个数。设枚举的子集划分有\(k\)个集合，那么容斥系数就是\({(-1)}^{k-1}(k-1)!\)。并把当前的方案数乘以容斥系数计入答案。
那么容斥系数是怎么来的呢？
记\(c_i\)为\(i\)个集合的容斥系数。对于每一个联通块个数为\(j\)的图，对枚举到的联通块个数为\(i\)的方案有\(S(j,i)\)的贡献。
我们只需要让\(\sum_{i=m}^nc(i)S(i,m)=[m=1]\)就可以了。
可以打表消元消除容斥系数。
时间复杂度：\(O(B_nn^2m)\)，其中\(B_n\)是Bell数的第\(n\)项。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[1010];
int n,m;
ull a[20][20];
int d[20];
ull ans=0;
ull pw[70];
ull fac[70];
ull c[70];
void dfs(int x,int y)
{
if(x>n)
{
int i,j,k;
for(i=0;i<m;i++)
c[i]=0;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(d[i]!=d[j])
{
ll s=a[i][j];
for(k=m-1;k>=0;k--)
if(s&(1ll<<k))
{
if(!c[k])
{
c[k]=s;
break;
}
s^=c[k];
}
}
int num=0;
for(i=0;i<m;i++)
if(!c[i])
num++;
ans+=pw[num]*fac[y-1]*(y&1?1:-1);
return;
}
int i;
for(i=1;i<=y;i++)
{
d[x]=i;
dfs(x+1,y);
}
d[x]=y+1;
dfs(x+1,y+1);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&m);
int i,j,k;
int len;
fac[0]=1;
pw[0]=1;
for(i=1;i<=m;i++)
pw[i]=pw[i-1]<<1;
for(i=1;i<=m;i++)
{
scanf("%s",s+1);
if(i==1)
{
len=strlen(s+1);
for(j=2;j<=10;j++)
if(j*(j-1)/2==len)
break;
n=j;
}
int t=0;
for(j=1;j<=n;j++)
for(k=j+1;k<=n;k++)
if(s[++t]=='1')
a[j][k]|=1ll<<(i-1);
}
for(i=1;i<=n;i++)
fac[i]=fac[i-1]*i;
dfs(1,0);
printf("%llu\n",ans);
return 0;
}
