[BZOJ4671]异或图 – xjr01 – 博客园
考虑先算一些限制少的情况
gi表示把n个点的图，划分成i个连通块的方案数
连通块之间不连通很好处理（怎么处理看下边），但是内部必须连通，就很难办了
所以再降低条件，fi表示，把n个点的图，划分成i个”连通块”，保证连通块之间不会有边相连，但是内部可以不连通的方案数
fi计算方法如下：
用Bell(n)的复杂度枚举集合划分，然后相邻集合之间不能连边，
然后考虑凑出符合这个集合划分的图有多少个，异或高斯消元，xi表示第i个图选择与否，如果必须不选，等号右边就是0，否则不管。
求自由元个数
fi和gi的关系：
就是枚举到底是有几个连通块
然后斯特林反演：
虽然往上枚举，但是式子证明思路是一样的，(-1)项的指数只要保证在所谓[n=m]时候是偶数就好了
高斯消元也可以换成线性基
每个图一个元素。每个线性基的位表示这个图这个边有没有，并且再和这次必要的边取&
要求多少个子集xor为全0
线性基之后，2^(s-sz）即可。
代码：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
#define int long long
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int M=;
const int N=;
int n,m;
int edge[M][][];
ll f[*];
ll t[N];
int ans[M];
char s[N*N];
ll id[N];
int vis[*];
ll Guass(int n){
memset(ans,-,sizeof ans);
memset(vis,,sizeof vis);
// for(reg i=1;i<=n;++i){
// for(reg j=1;j<=m;++j){
// cout<<f[i][j]<<" ";
// }cout<<" = "<<f[i][m+1]<<endl;
// }
// cout<<endl;
int free=;
for(reg i=;i<=m;++i){
int id=;
for(reg j=;j<=n;++j){
if((!vis[j])&&(f[j]&(1LL*<<(i-)))) id=j;
}
if(!id){
++free;continue;
}
vis[i]=;
if(id!=i) swap(f[i],f[id]);
for(reg j=;j<=n;++j){
if(j==i) continue;
if(!vis[j]&&(f[j]&(1LL*<<(i-)))){
f[j]^=f[i];
}
}
}
return (1LL*<<free);
}
void dfs(int x,int sz){
if(x==n+){
//cout<<" x "<<x<<" sz "<<sz<<endl;
memset(f,,sizeof f);
int cnt=;
for(reg i=;i<=n;++i){
for(reg j=i+;j<=n;++j){
if(id[i]!=id[j]){
++cnt;
for(reg k=;k<=m;++k){
if(edge[k][i][j]) f[cnt]|=(1LL*<<(k-));
}
}
}
}
// cout<<" cnt "<<cnt<<endl;
t[sz]+=Guass(max(cnt,m));
return;
}
for(reg i=;i<=sz;++i){
id[x]=i;
dfs(x+,sz);
id[x]=;
}
id[x]=sz+;
dfs(x+,sz+);
id[x]=;
}
void calc(int l){
for(n=;n<=;++n){
if(n*(n-)/==l) break;
}
}
int main(){
rd(m);
for(reg i=;i<=m;++i){
scanf("%s",s+);
int l=strlen(s+);
if(!n) calc(l);
int t=;
for(reg j=;j<=n;++j){
for(reg k=j+;k<=n;++k){
++t;
edge[i][j][k]=edge[i][k][j]=s[t]-'';
}
}
}
dfs(,);
ll ans=,jie=;
for(reg i=;i<=n;++i){
if(i&){
ans+=jie*t[i];
}else{
ans-=jie*t[i];
}
jie*=i;
}
printf("%lld",ans);
return ;
}}
signed main(){
Miracle::main();
return ;
}/*
Author: *Miracle*
Date: 2019/2/16 21:40:44
*/
总结：
找到两个数组f，g
f范围宽松好统计，g范围严格难统计但是和答案有直接关系，
这样，只要得到f和g的关系，就可以找到答案！
异或下线性方程组的自由元个数：
先变成n*(n+1)的矩阵
然后高斯消元，如果某一个id找不到，那么一定是自由元了，计数器++
注意，每次找i和消除必须在全局位置，并且用一个vis标记表示是否还能动
最后削成的上三角矩阵，除了无解情况，剩下的一定有唯一解
