神仙题啊神仙题
显然这个东西一脸不可求的样子啊，这种东西我们显然需要搞一个容斥什么的
于是设(g_i)表示至少存在(i)个联通块（联通块内部的边没有要求，联通块和联通块之间不存在边）的方案数，(f_i)表示恰有(i)个联通块
有
[g_x=sum_{i=x}^negin{Bmatrix}i\xend{Bmatrix}f_i
]
即我们对于那些联通块个数多于(x)个的情况，可以把这(i)个联通快分成(k)组，每一组作为一个新的“联通块”，于是后面那个是一个第二类斯特林数
于是根据斯特林反演，有
[f_x=sum_{i=x}^n(-1)^{i-x}egin{bmatrix}i\xend{bmatrix}g_i
]
对于这道题我们要求的就是(f_1)
[f_1=sum_{i=1}^n(-1)^{i-1}(i-1)!g_i
]
现在要做的就是求(g_i)了
我们注意到这张图的点数很少，我们甚至可以爆搜一下每个点分到哪一个集合里去，我们就可以扫一遍每一张图，对于一条连接两个不同集合的边，我们把这条边用二进制状态存一下，现在只需要求出有多少个子集异或和为(0)就好了
这个问题可以用线性基来解决，结论就是如果有(x)个元素不能插入线性基，那么异或和为(0)的子集数量就是(2^x)个
这个可以这样理解啊，我们把不能插入线性基的元素拿出来，这些元素构成的子集个数是(2^x)个，显然(2^x)个子集也都能被线性基表示出来，我们把线性基里表示这些子集的那些元素和这些子集异或，就得到了(2^x)个异或和为(0)的子集，由于线性基里没有任何一个子集异或和为(0)，于是总共就是(2^x)个
这样对于每一个不能插入线性基的元素都有两种选择，于是子集个数是(2^x)种
代码
#include<cstdio>
#include<cstring>
#define re register
#define LL long long
int m,n,len,t;LL ans,cnt;
char S[1005];
LL fac[15],pw[105],lb[50],g[15],b[66];
int a[15],vis[66][15][15];
inline int ins(LL x) {
for(re int i=t-1;i>=0;--i)
if(x>>i&1) {
if(!lb[i]) {lb[i]=x;return 1;}
x^=lb[i];
}
return 0;
}
void dfs(int x,int now) {
if(x==n+1) {
t=0;memset(lb,0,sizeof(lb));
for(re int k=1;k<=m;k++) {
b[k]=t=0;
for(re int i=1;i<=n;i++)
for(re int j=i+1;j<=n;j++)
if(a[i]!=a[j]) b[k]|=(1ll*vis[k][i][j]<<t),t++;
}
int tot=0;
for(re int k=1;k<=m;k++) if(!ins(b[k])) ++tot;
g[now]+=pw[tot];
return;
}
for(re int i=1;i<=now;i++) a[x]=i,dfs(x+1,now);
a[x]=now+1;dfs(x+1,now+1);
}
int main() {
scanf("%d",&m);
for(re int k=1;k<=m;k++) {
scanf("%s",S+1);len=strlen(S+1);
if(!n) {n=1;while(n*(n-1)/2!=len) n++;}
int now=1;
for(re int i=1;i<=n;i++)
for(re int j=i+1;j<=n;j++)
vis[k][i][j]=S[now]-'0',now++;
}
fac[0]=1;pw[0]=1;
for(re int i=1;i<=m;i++) pw[i]=pw[i-1]+pw[i-1];
for(re int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i;
dfs(1,0);
for(re int i=1;i<=n;i++) ans+=1ll*((i&1)?1:-1)*fac[i-1]*g[i];
printf("%lld
",ans);
return 0;
}