【BZOJ4671】(斯特林反演)

题目

【BZOJ4671】异或图

很有意思的题

做法

直接处理显然很难，我们考虑范围扩大以求容斥或反演这类的帮助

$f_i$表示至少有$i$个联通块的方案，形如设立$i$个联通块轮廓，联通块内连边随意，联通块与联通块之间无连边

$g_i$表示恰好有$i$个联通块的方案，形如设立$i$个联通块轮廓，在保证内部联通的情况下，外部块与块间无连边

显然：$$f_x=\sum\limits_{i=x}^n\begin{Bmatrix}i\x\end{Bmatrix}g_i$$

根据斯特林反演：$$g_x=\sum\limits_{i=x}^n (-1)^{i-x}\begin{bmatrix}i\x\end{bmatrix}f_i$$

故$g_1=\sum\limits_{i=1}^n (-1)^{i-1}\begin{bmatrix}i\\1\end{bmatrix}f_i$

而$\begin{bmatrix}i\\1\end{bmatrix}$是阶乘形式：$\begin{bmatrix}i\\1\end{bmatrix}=(i-1)!$

化简答案为：$g_1=\sum\limits_{i=1}^n (-1)^{i-1}(i-1)!f_i$

考虑$f_i$如何求出：状压点所属联通块状态，则我们要选择图集使块与块之间无边，考虑枚举每个图的$S$表示点与点之间的连边(不属同一联通块)，我们压到线性基里去，$ele$表示线性基元素，这些元素是不能选择的(相异)，故答案为$2^{N-ele}$

Code

#include<bits/stdc++.h>

typedef int LL;

const LL maxn=109;

LL N,n;

LL G[maxn][maxn][maxn],a[maxn];

char s[maxn];

long long ans,p[maxn],S,fac[15];

void Dfs(LL x,LL up){

	if(x==n+1){

		memset(p,0,sizeof(p)); LL ele(0);

		for(LL i=1;i<=N;++i){

			S=0; LL tot(0);

			for(LL j=1;j<=n;++j)

			    for(LL k=j+1;k<=n;++k)

			        if(a[k]!=a[j]){

			        	S|=(1ll<<tot)*G[i][j][k];

			        	++tot;

					}

			for(LL j=0;j<tot;++j){

				if(S&(1ll<<j)){

					if(!p[j]){

						p[j]=S;

						++ele;

						break;

					}else

					    S^=p[j];

				}

			}

		}

		ans+=1ll*((up&1)?1:-1)*fac[up-1]*(1ll<<N-ele);

		return;

	}

	for(LL i=1;i<=up+1;++i){

		a[x]=i;

		Dfs(x+1,std::max(up,i));

	}

}

int main(){

	scanf("%d",&N);

	for(LL i=1;i<=N;++i){

		scanf(" %s",s+1);

		LL len(strlen(s+1));

		if(!n){

		    n=1;

		    for(;n*(n-1)/2!=len;++n);

		}

		LL now(0);

		for(LL j=1;j<=n;++j) for(LL k=j+1;k<=n;++k) G[i][j][k]=s[++now]-'0';

	}

	fac[0]=fac[1]=1; for(LL i=2;i<=n;++i) fac[i]=fac[i-1]*i;

	Dfs(1,0);

	printf("%lld",ans);

	return 0;

}