[bzoj4671]异或图——容斥＋斯特林数反演＋线性基

题目大意：

定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.

现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异或为一个连通图?

思路：

这种计算连通图的个数的题目一般情况下考虑容斥。

由于一个图的联通不好直接计算，但是对于点集的划分，我们要使它不连通会容易得多。

于是在发现虽然\(s\)较大，但是\(n\)很小的情况下，我们可以枚举这\(n\)个点的划分，然后对于每一个划分，强制不同集合中的点不连通，同一个集合中的点任意，然后计算满足条件的图的个数。

这个时候我们的容斥系数应该满足这样的条件，对于一个拥有\(m\)个联通块的图，需要满足

\[
\sum_{i=1}^{m}{m\brace i}\times f_i=[m=1]
\]

然后考虑直接用斯特林数反演来求出\(f_i:\)

\[
f_i=(-1)^{(i-1)}\times (i-1)!
\]

接下来考虑如何计算满足各个集合中的点不连通的方案数，这里把跨越集合的边单独提出来，每条边的存在状况可以看成是一个\(01\)串，现在即求这\(s\)个01串的异或和中有多少个\(0\)。

于是我们可以直接对这\(s\)个数建立线性基，如果最后线性基中有\(c\)个元素，那么一共有\(2^{s-c}\)种方式可以使异或和为０。

#include
#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<#define fi first
#define se second
#define mk make_pair
#define pb push_back
typedef long long ll;
using namespace std;
void File(){
freopen("bzoj4671.in","r",stdin);
freopen("bzoj4671.out","w",stdout);
}
templatevoid read(T &_){
_=0; T f=1; char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())_=(_<<1)+(_<<3)+(c^'0');
_*=f;
}
const int maxn=10+10;
const int maxs=60+10;
int s,n,bel[maxn],q[maxs],cnt;
char str[maxs][maxs];
ll num[maxs],fac[maxs],f[maxs],ans,b[maxs];
void init(){
read(s);
REP(i,1,s)scanf("%s",str[i]+1);
int len=strlen(str[1]+1);
REP(i,2,10)if(i*(i-1)/2==len)n=i;
fac[0]=1;
REP(i,1,10)fac[i]=fac[i-1]*i;
REP(i,1,10)f[i]=((i-1)%2 ? -1 : 1)*fac[i-1];
}
void calc(int tot){
REP(i,1,s){
num[i]=0;
REP(j,1,cnt)num[i]=num[i]<<1|(str[i][q[j]]^'0');
}
REP(i,1,cnt)b[i]=0;
int c=0;
REP(i,1,s){
DREP(j,cnt,1){
if((1ll<<(j-1))&num[i]){
if(!b[j]){++c;b[j]=num[i];break;}
num[i]^=b[j];
}
}
}
ans+=f[tot]*(1ll<<(s-c));
}
void dfs(int k,int tot){
if(k>n){
cnt=0;
int id=0;
REP(i,1,n)REP(j,i+1,n){
++id;
if(bel[i]!=bel[j])
q[++cnt]=id;
}
calc(tot);
return;
}
bel[k]=tot+1;
dfs(k+1,tot+1);
REP(i,1,tot){
bel[k]=i;
dfs(k+1,tot);
}
}
int main(){
File();
init();
dfs(1,0);
printf("%lld\n",ans);
return 0;
}