[BZOJ4671]異或圖

description

BZOJ
定義兩個結點數相同的圖\(G1\)與圖\(G2\)的異或為一個新的圖\(G\),
其中如果\((u,v)\)在\(G1\)與\(G2\)中的出現次數之和為\(1\),
那么邊\((u,v)\)在\(G\)中, 否則這條邊不在\(G\)中.
現在給定\(s\)個結點數相同的圖\(G1...s\),設\(S={G1,G2,...,Gs},\)
問\(S\)有多少個子集的異或為一個連通圖.
\(n\le 10,s\le 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}\begin{Bmatrix}m\\k\end{Bmatrix}g(m)\]

考慮每個連通塊個數\(=m\)的方案,因為當前假定有\(k\)個可能連通塊,
那么這\(m\)個連通塊會被劃分為\(k\)個無序集合,因此重復計算了\(\begin{Bmatrix}m\\k\end{Bmatrix}\)次。

斯特林反演即可。
\[g(k)=\sum_{m=k}^{n}(-1)^{m-k}\begin{bmatrix}m\\k\end{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\n",ans);return 0;
}