打不开爆炸(OJ)就不挂网址了
直接求不好求，考虑容斥
设(f_i)表示有(i)个联通块的答案，(g_i)表示有(i)部分不与外界联通的答案
有方程
[g_i=sumlimits_{j=i}^{n}egin{Bmatrix}j\iend{Bmatrix}f_j
]
根据斯特林反演有
[f_i=sumlimits_{j=i}^{n}(-1)^{j-i}egin{bmatrix}j\iend{bmatrix}g_j
]
最终答案是
[f_1=sumlimits_{j=1}^{n}(-1)^{j-1}egin{bmatrix}j\1end{bmatrix}g_j
]
[f_1=sumlimits_{j=1}^{n}(-1)^{j-1}(j-1)!g_j
]
点数(le 10)所以考虑直接大力枚举子集划分
我们强制不同的集合之间边不存在，然后将不同图的集合之间连边情况转为二进制串插入线性基
设集合数量为(t)，那么最后(g_t)的数量是不同图之间异或等于(0)的方案数，假设插入线性基中的数量为(c)，那么答案为(2^{s-c})
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=110;
int n,num,ans,sum;
int inv[N],fac[N],ifac[N];
char s[N];
int g[N][N][N],a[N];
int p[N];
inline void dfs(int x,int up)
{
if(x==num)
{
memset(p,0,sizeof(p));
int sum=0;
for(int i=1;i<=n;++i)
{
int ret=0,tot=0;
for(int j=1;j<=num;++j)
{
for(int k=j+1;k<=num;++k)
{
if(a[j]!=a[k]) ret|=(g[i][j][k]<<tot);
++tot;
}
}
for(int j=tot;~j;--j) if(ret>>j&1)
{
if(!p[j])
{
++sum;p[j]=ret;
break;
}
ret^=p[j];
}
}
if(up&1) ans+=fac[up-1]*(1ll<<(n-sum));
else ans-=fac[up-1]*(1ll<<(n-sum));
return;
}
for(int i=1;i<=up+1;++i)
{
a[x+1]=i;
dfs(x+1,max(i,up));
}
}
inline void main()
{
n=read();
for(int i=fac[0]=1;i<12;++i) fac[i]=fac[i-1]*i;
for(int len,cnt,i=1;i<=n;++i)
{
scanf("%s",s+1);
len=strlen(s+1),cnt=0;
for(int j=1;!num;++j)
if(j*(j-1)==2*len) num=j;
for(int j=1;j<=num;++j)
for(int k=j+1;k<=num;++k)
g[i][j][k]=s[++cnt]-'0';
}
a[1]=1;
dfs(1,1);
printf("%lld
",ans);
}
}
signed main()
{
red::main();
return 0;
}