题意

定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与
G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.
现在给定 s 个结点数相同的图 G1…s, 设 S = {G1, G2, … , Gs}, 请问 S 有多少个子集的异或为一个连通图?

题解

这题的话，我们可以枚举联通块
然后不同块的一定不能连边这个东西，就相当于给了若干个异或方程组
问你自由元个数吧方程都拿出来，高斯消元就可以了
因为这个东西，方程之间的运算是可以“状压”的，所以可以省去一个n的复杂度
然后斯特林反演的系数$(-1)^{i-1}*(i-1)!$
证明就不给了。。记下来也可以

CODE:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=15;
LL s;
char ss[N*N];
LL n=0;
LL f[62][N][N];
LL JC[N];
LL ans;
LL bel[N];
LL h[N*N];
LL calc ()
{LL tot=0;for (LL u=1;u<=n;u++)for (LL i=u+1;i<=n;i++)if (bel[u]!=bel[i]){LL lalal=0;for (LL j=0;j<s;j++)lalal=lalal|(1LL<<j)*f[j][u][i];//  printf("%lld\n",lalal);h[++tot]=lalal;}LL now=1;LL lalal=0;for (LL u=s-1;u>=0;u--){//  printf("ooo:%lld %lld\n",now,tot);for (LL i=now;i<=tot;i++){//printf("k:%lld %lld\n",h[i],h[]);if ((h[i]>>u)&1LL)  {swap(h[i],h[now]);break;}}//  printf("%lld %lld %lld %lld\n",u,now,h[now],(h[now]>>u)&1);if (now<=tot&&(h[now]>>u)&1LL)  {for (int i=now+1;i<=tot;i++)if ((h[i]>>u)&1LL)h[i]^=h[now];now++;}else lalal++;}//printf("OZY:%lld\n",lalal);return 1LL<<lalal;
}
void dfs (LL x,LL id)
{if (x==n+1){LL t;if (id&1) t=JC[id-1];else t=-JC[id-1];//  printf("TYB:%lld %lld %lld\n",x,id,t);ans=ans+t*calc();return ;}for (LL u=1;u<=id;u++){bel[x]=u;dfs(x+1,id);}bel[x]=id+1;dfs(x+1,id+1);
}
int main()
{scanf("%lld",&s);for (LL u=0;u<s;u++){scanf("%s",ss);LL len=strlen(ss);for (LL j=1;n==0;j++)if (j*(j-1)/2==len)n=j;LL xx=0;for (LL i=1;i<=n;i++)for (LL j=i+1;j<=n;j++){f[u][i][j]=ss[xx]-'0';xx++;}}
//  printf("%lld\n",n);JC[0]=1;for (LL u=1;u<=n;u++) JC[u]=JC[u-1]*u;ans=0;dfs(1,0);printf("%lld\n",ans);return 0;
}