[BZOJ4671]异或图

description

BZOJ
定义两个结点数相同的图(G1)与图(G2)的异或为一个新的图(G),
其中如果((u,v))在(G1)与(G2)中的出现次数之和为(1),
那么边((u,v))在(G)中, 否则这条边不在(G)中.
现在给定(s)个结点数相同的图(G1...s),设(S={G1,G2,...,Gs},)
问(S)有多少个子集的异或为一个连通图.
(nle 10,sle 60)

solution

考虑如何减掉图不连通的方案,此时图被分割成的连通块数一定大于一个。
先求出连通块数至少为(k)的方案数,那么枚举子集划分,(O(B_n),B_{10}=21147);
之后需要保证集合之间无连边,即(s)个图的异或不能和集合间对应边的集合(S)有交。
求集合与(S)的交集插入线性基,设线性基内的元素个数为(c),那么最后答案为(2^{s-c})。

这样我们得到了(f(x))表示连通块个数(ge x)的方案数。
设(g(x))表示连通块个数(=x)的方案数,那么要求的是(g(1))。
针对子集划分,我们有斯特林数。$$f(k)=sum_{m=k}^{n}egin{Bmatrix}mkend{Bmatrix}g(m)$$

考虑每个连通块个数(=m)的方案,因为当前假定有(k)个可能连通块,
那么这(m)个连通块会被划分为(k)个无序集合,因此重复计算了(egin{Bmatrix}m\kend{Bmatrix})次。

斯特林反演即可。

[g(k)=sum_{m=k}^{n}(-1)^{m-k}egin{bmatrix}m\kend{bmatrix}f(m) ]

[g(1)=sum_{m=1}^{n}(-1)^{m-1}(m-1)!f(m) ]

code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FL "a"
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int mod=998244353;
inline ll read(){
  ll data=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
  return data*w;
}
inline void file(){
  freopen(FL".in","r",stdin);
  freopen(FL".out","w",stdout);
}

int s,n,G[60][10][10],get[45],in[10];ll p[45],fac[11],ans;
void dfs(int x,int t){
  int i;
  if(x==n){
    int cnt=0,tot,g,j;ll tmp;
    memset(p,0,sizeof(p));memset(get,0,sizeof(get));
    for(g=0;g<s;g++){
      tmp=tot=0;
      for(i=0;i<n;i++)
	for(j=i+1;j<n;j++)
	  if(in[i]^in[j])tmp|=1ll*G[g][i][j]<<tot,tot++;
      for(i=0;i<tot;i++)
	if(tmp&1ll<<i){if(p[i])tmp^=p[i];else{p[i]=tmp;cnt++;break;}}
    }
    ans+=(t&1?1:-1)*fac[t-1]*(1ll<<s-cnt);
    return;
  }
  for(i=1;i<=t+1;i++)in[x]=i,dfs(x+1,max(i,t));
}

map<int,int>M;
int main()
{
  s=read();
  int i,j,g,pp;string c;
  for(i=fac[0]=1;i<=10;i++)fac[i]=1ll*fac[i-1]*i;
  for(i=2;i<=10;i++)M[i*(i-1)/2]=i;
  for(g=0,pp;g<s;g++){
    cin>>c;n=M[c.length()];pp=0;
    for(i=0;i<n;i++)
      for(j=i+1;j<n;j++)
	G[g][i][j]=c[pp++]-48;
  }
  dfs(0,0);
  printf("%lld
",ans);
  return 0;
}