注意
线性基空间要开够，1左移超过31位应该写成1LL
前置芝士
斯特林反演
斯特林反演有两种形式（和二项式反演类似）
[G_n=sum_{i=1}^nleft{egin{matrix}n\iend{matrix}
ight}F_iRightarrow F_n=sum_{i=1}^n(-1)^{n-i}left[egin{matrix}n\iend{matrix}
ight]G_i
]
[G_k=sum_{i=k}^nleft{egin{matrix}i\kend{matrix}
ight}F_iRightarrow F_k = sum_{i=k}^n(-1)^{i-k}left[egin{matrix}i\kend{matrix}
ight]G_i
]
思路
利用第一种形式
设(g_i)表示至少有i个连通块，用(f_i)表示恰好有i个联通块的方案数
首先(ans=sum_{i=1}^n T_i F_i)，先胡乱写一个式子，然后考虑(T_i)这个容斥系数到底是什么东西
每项被计算的次数是(left{egin{matrix}n\iend{matrix}
ight})
因为最后的答案中应该只包含1个连通块的贡献，所以可以得到一个式子
[sum_{i=1}^nleft{egin{matrix}n\iend{matrix}
ight}T_i=left[n=1
ight]
]
斯特林反演一下有
[sum_{i=1}^nleft[egin{matrix}n\iend{matrix}
ight][n=1]=T_n
]
所以
[T_i=(-1)^{n-i}(n-i)!
]
利用第二种形式
容易发现直接求并不好求，考虑反演一发
对于集合划分问题，一般都使用斯特林反演
设(g_i)表示至少有i个连通块，用(f_i)表示恰好有i个联通块的方案数
对于(g_i)我们可以枚举一个子集的划分，不在同一个子集中的点之间一定没有边，在同一个子集中的点之间可以随意连边，这样就保证了如果划分了i个集合，那么最少会有i个连通块
接下来考虑系数，假设当前恰好划分出i个连通块，为了满足(g_k)的条件，相当于要把这i个连通块划分到k个新的连通块中，所以每个(f_i)会产生(left{egin{matrix}i\kend{matrix}
ight})的贡献
所以能够得到(f_i)和(g_i)的关系
[g_k=sum_{i=k}^n left{egin{matrix}i\kend{matrix}
ight}f_i
]
根据斯特林反演公式
得到
[f_k=sum_{i=k}^n(-1)^{i-k}left[egin{matrix}i\kend{matrix}
ight]g_i
]
因为要求(f_1)
所以得到
[egin{align}f_1&=sum_{i=1}^n(-1)^{i-1}left[egin{matrix}i\1end{matrix}
ight]g_i\&=sum_{i=1}^n(-1)^{i-1}(i-1)!g_iend{align}
]
利用反演得出的柿子求解
第一种和第二种得出的式子是相同的，考虑如何计算(G_i)
dfs计算划分之后，把每个数都当成一个二进制数，确定每个图上没有那些边相连后，将其插入线性基中，最后求异或和为0的方案数，求异或和为零的方案数相当于要找到线性无关的组的个数，剩下的可以随便取，所以(g_i=2^{n-t})t是线性无关的个数
代码
#include <cstdio>
#include <cstring>
#include <cstring>
#define int long long
using namespace std;
int n,T,has[100][20][20],belong[20],jd[100],nob,jc[40],ans=0;
char s[200];
void init(void){
nob=0;
memset(jd,0,sizeof(jd));
}
void insert(int s){
for(int i=62;i>=1;i--){
if((s>>(i-1))&1LL){
if(!jd[i]){
nob++;
jd[i]=s;
break;
}
else
s^=jd[i];
}
}
}
void init_jc(void){
jc[0]=1;
for(int i=1;i<=20;i++)
jc[i]=(jc[i-1]*i);
}
void dfs(int num,int id){
// printf("%lld %lld
",num,id);
if(num==n){
init();
for(int i=1;i<=T;i++){
int S=0,mid=0;
for(int j=1;j<=n;j++)
for(int k=j+1;k<=n;k++){
mid++;
if(belong[j]!=belong[k]){
S|=(1LL<<(mid-1))*has[i][j][k];
}
}
insert(S);
}
ans+=(((id-1)&1)?-1:1)*(jc[id-1])*(1LL<<(T-nob));
return;
}
for(int i=1;i<=id;i++){
belong[num+1]=i;
dfs(num+1,id);
belong[num+1]=0;
}
belong[num+1]=id+1;
dfs(num+1,id+1);
belong[num+1]=0;
}
signed main(){
init_jc();
scanf("%lld",&T);
for(int i=1;i<=T;i++){
scanf("%s",s+1);
int l=strlen(s+1);
// printf("l=%d
",l);
if(!n)
for(int j=1;;j++)
if(j*(j-1)==2*l){
n=j;
break;
}
int mid=1;
for(int j=1;j<=n;j++)
for(int k=j+1;k<=n;k++)
has[i][j][k]=has[i][k][j]=s[mid++]-'0';
}
dfs(0,0);
printf("%lld
",ans);
return 0;
}