Description：

现在给定 $|S|$ 个结点数相同的图 $G_1,\dots,G_s$ , 设 $S={G_1,G_2,\dots,G_s}$ ，请问 $S$ 有多少个子集的异或为一个连通图？

$1\leqslant n\leqslant 10,1\leqslant |S|\leqslant 60$

Solution：

强制连通不好做，可以考虑强制不连通，因此先容斥，那么我们就会希望每一种连通的图在最后刚好被计算了 $1$ 次，而不连通的图被计算了 $0$ 次，设 $f[i]$ 表示恰好有 $i$ 个联通块的方案数，那么 $ans=f[1]$ ， $g[i]$ 表示划分出了 $i$ 个联通块，再把这些联通块随便划分的方案数之和，不难发现 $\sum g[i]\geqslant$ 划分出至少 $i$ 个点的方案数，那么 $f$ 和 $g$ 的关系是： $$ g[i]=\sum_{k=i}^n\begin{Bmatrix}k\\i\end{Bmatrix}f[k] $$ 也就是说一个 $k$ 个连通块的划分，显然我们有 $S_2(k,i)$ 种方式把它划分成 $i$ 个连通块的划分，他会对这些划分每种划分贡献一，于是对 $g$ 的总的贡献就是 $S_2(k,i)$ 。

换个说法理解就是： $$ g[i]=\sum_{划分}g'[划分](该划分连通块个数为i) $$ $g'[划分]$ 表示现在有一个划分，然后再把这个划分随便划分的方案数。

然后就比较容易理解了，根据斯特林反演定理： $$ g[n]=\sum_{i=1}^n\begin{Bmatrix}n\\i\end{Bmatrix}f[i]\Longleftrightarrow f[n]=\sum_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}g[i] $$ 显然： $$ f[1]=\sum_{i=1}^n\begin{bmatrix}i\\1\end{bmatrix}(-1)^{i-1}g[i] $$ 这是因为斯特林反演定理对于超集也是成立的，类似莫比乌斯反演。

然后： $$ \begin{align} f[1]&=\sum_{i=1}^n\begin{bmatrix}i\\1\end{bmatrix}(-1)^{i-1}g[i]\\ &=\sum_{i=1}^n(i-1)!(-1)^{i-1}g[i] \end{align} $$ 最后再考虑怎么求 $g$ ，我们可以用贝尔数的时间复杂度来枚举集合划分，然后对于每种集合划分我们都可以计算出 $g'[划分]$ ，于是就可以累加到 $g[i]$ 里了，具体统计的方案是对于每一条跨越集合的边，我们都可以列出一个方程： $$ [e\in G_1]G_1(e)\text{ xor }[e\in G_2]G_2(e)\cdots [e\in G_{|S|}]G_{|S|}(e)=0 $$ 也就是这些值都为零的方案数，把他们插入线性基，答案显然是 $2$ 的自由元个数次方即 $2^{e-cnt}$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int s;

#define MAXN 11

#define MAXS 61

int n = 0;

int g[MAXS][MAXN][MAXN];

char c[MAXN * MAXN];

typedef long long ll;

ll fac[MAXN];

int belong[MAXN];

ll ans = 0;

ll d[MAXN * MAXN];

void dfs(int x,int t)

{

	if(x == n + 1)

	{

		memset(d,0,sizeof(d));

		int cnt = 0;

		int tot;

		for(int k = 1;k <= s;++k)

		{

			tot = 0;ll S = 0;

			for(int i = 1;i <= n;++i)for(int j = i + 1;j <= n;++j)

				if(belong[i] != belong[j])S ^= (1ll << tot) * g[k][i][j],++tot;

			for(int i = 0;i < tot;++i)

			{

				if(S & (1ll << i))

				{

					if(d[i] == 0){++cnt;d[i] = S;break;}

					else S ^= d[i];

				}

			}

		}

		ans = ans + fac[t - 1] * ((t & 1) ? 1ll : -1ll) * (1ll << (s - cnt));

	}

	else

	{

		for(int i = 1;i <= t + 1;++i)

		{

			belong[x] = i;

			dfs(x + 1,max(i,t));

		}

	}

	return;

}

int main()

{

	scanf("%d",&s);

	for(int k = 1;k <= s;++k)

	{

		scanf("%s",&c);

		int cur = 0;

		if(n == 0)n = (1 + sqrt(1 + 8 * strlen(c))) / 2;

		for(int i = 1;i <= n;++i)for(int j = i + 1;j <= n;++j)g[k][i][j] = c[cur++] - '0';

	}

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i;

	dfs(1,0);

	cout << ans << endl;

	return 0;

}