我能说什么！抽象了这！
看到 \(n\le 10\) 的黑题顿感大事不妙。
我们考虑设 \(f(i)\) 表示将 \(n\) 个点划分为至少 \(i\) 个连通块时的方案数。我们可以暴力枚举每个点在哪个连通块里。划分方案是 \(Bell(n)\le 21147\) 的。
显然的，相同块内暂时忽略，不同块间不能有边。于是我们将每张图的新边集定为这张图中所有的违法边。当一些新边集异或和为 \(0\) 时，表明我们找到了一个合法解。直接线性基加新边集。若向线性基中成功加入了 \(k\) 个新边集，那么对答案的贡献就是 \(2^{s-k}\)。这一部分的时间复杂度为 \(O(Bell(n)sn^2)\)，注意卡常。
设 \(g(i)\) 表示 \(n\) 个点恰好划分成 \(i\) 个连通块时的方案数，那么我们可以将 \(i\) 个连通块放入 \(j\) 个集合中，每个集合再形成一个假连通块。这实际上就是 \(g(i)\) 对 \(f(j)\) 的贡献。将其表示为等式，即为：
\[f(m)=\sum_{i=m}^n\begin{Bmatrix}i\\m\end{Bmatrix}g(i) \]可以直接高斯消元，也可以根据斯特林反演，得到：
\[g(1)=\sum_{i=1}^n(-1)^{i-1}\begin{bmatrix}i\\1\end{bmatrix}f(i) \]\[=\sum_{i=1}^n(-1)^{i-1}(i-1)!f(i) \]总体时间复杂度 \(O(Bell(n)sn^2)\)。
#include<bits/stdc++.h>
#define bi(x) x==1?2:x==3?3:x==6?4:x==10?5:x==15?6:x==21?7:x==28?8:x==36?9:10
#define int long long
using namespace std;
int t,n,len,a[15],num[50],f[15],sm[65];
int vs[65][50],tw[65];string s;
int add(int x){
for(int i=len-1;~i;--i){
if(!((x>>i)&1)) continue;
if(num[i]) x^=num[i];
else return num[i]=x,1;
}return 0;
}void check(int x){
int tot=0;
for(int i=0;i<len;++i) num[i]=0;
for(int j=1,k=0;j<=n;++j)
for(int l=j+1;l<=n;++l,++k) if(a[j]^a[l])
for(int i=1;i<=t;++i) sm[i]|=(vs[i][k]<<k);
for(int i=1;i<=t;i++) tot+=(!add(sm[i])),sm[i]=0;
f[x]+=tw[tot];
}void dfs(int x,int y){
if(x>n) return check(y);
for(a[x]=1;a[x]<=y;++a[x]) dfs(x+1,y);
dfs(x+1,y+1);
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t,tw[0]=1;
for(int i=1;i<=60;++i) tw[i]=tw[i-1]*2;
for(int i=1;i<=t;++i){
cin>>s;
if(!n) len=s.size(),n=bi(len);
for(int j=0;j<len;++j)
vs[i][j]=s[j]-'0';
}dfs(1,0);int ans=0,jc=1;
for(int i=1;i<=n;++i)
ans+=((i&1)?1:-1)*jc*f[i],jc*=i;
cout<<ans;
return 0;
}