[UR #14]人类补完计划

计数好题。

题意：给定简单无向图 \(G=(V,E),|V|=n,|E|=m\)，有 \(n\leq 16,m\leq {n\choose 2}\)，求所有为基环树的子图的权值之和。一个基环树的权值定义为 \(2^w\)，其中 \(w\) 是非叶子节点的个数。

用这篇博客提到的最小元状压 DP 的技巧，我们可以轻松地在 \(O(2^n n^2)\) 的时间内求出一个点子集 \(S\) 成为环的方案数 \(cyc_S\)。由于我们钦定最小元是环起点，两个方向分别被 DP 了一次，所以答案记得 \(\div 2\)。需要注意仅有两个点的不算环！

我们现在先考虑不带权值计算一个点子集成为基环树的方案数，设其为 \(dp_S\)。一个暴力的想法是枚举 \(T\subset S\) 将 \(T\) 作为环缩成一个点跑矩阵树，复杂度 \(O(3^n n^3)\)，可以拿 30 分。

我们得到了 \(dp_S\) 如何计算带权值的方案呢？由于权值跟叶子数量有关，一个经典套路就是钦定一些叶子上容斥。钦定 \(T\subset S\) 必须当叶子，\(S/T\) 部分随便取一颗基环树，那么 \(S/T,T\) 间连边方案数就是 \(T\) 中的点在 \(S/T\) 中的度数乘积，不妨记为 \(\text{cross}(T,S/T)=\)，还有对叶子的 \((-1)^{|T|}\) 的容斥系数。那么有：

\[\begin{aligned}
res&=\sum_{S\subset V} \sum_{T\subset S} dp_{S/T} 2^{|S/T|} (-1)^{|T|} \text{cross}(T,S/T)\\
&=\sum_{S\subset V} \sum_{T\subset S} dp_{S/T} 2^{|S/T|} \prod_{x\in T} -\text{cross}(x,S/T)\\
&=\sum_{P\subset V} \sum_{S\supset P} dp_{P} 2^{P} \prod_{x\in S/P} -\text{cross}(x,P)\\
&=\sum_{P\subset V} dp_{P} 2^{P} \prod_{x\in V/P} 1-\text{cross}(x,P)\\
\end{aligned}
\]

如果能更快地求 \(dp_{P}\)，那么后面的部分就可以在 \(O(2^n n)\) 的时间内解决。

接下来有两种方式求 \(dp\) 数组。

继续对叶子容斥

就是UOJ 官解算法五和虞皓翔做法。

我们不妨设 \(f_{S,T}\) 表示点集为 \(S\)，叶子点集为 \(T\) 的基环树方案数。然后依然考虑钦定部分叶子。

设 \(F_{S,T}=\sum_{T'\supset T} f_{S,T'}\)，相当于算钦定 \(T\) 集合的方案数，\(\text{IFWT}\)（高维差分）回去就是 \(f_{S,T}=\sum_{T'\supset T} F_{S,T'}(-1)^{|T'/T|}\)。

注意到 \(dp_S=\sum_{T\subset S} f_{S,T}=F_{S,\emptyset}\)，以及 \(cyc_S=f_{S,\emptyset}=\sum_{T\subset S} F_{S,T}(-1)^{|T|}\)。只需要算出所有 \(T\) 非空的 \(F_{S,T}\) 就可以算出 \(dp_{S}\)。

而 \(T\) 若非空，我们根据容斥的组合意义容易导出：\(F_{S,T}=\text{cross}(T,S/T) dp_{S/T}\)。

带入上述式子解出 \(dp_S\)，我们有：

\[dp_S=cyc_S-\sum_{T\subset S,T\neq \emptyset} \text{cross}(T,S/T) dp_{S/T} (-1)^{|T|}
\]

可以在 \(O(3^n)\) 的时间内愉快地计算。

注意为了递推 \(\text{cross}\) 函数，我们需要枚举 \(S/T\) 然后刷表。

#include <cstdio>

#include <vector>

using namespace std;

int read(){

	char c=getchar();int x=0;

	while(c<48||c>57) c=getchar();

	do x=(x<<1)+(x<<3)+(c^48),c=getchar();

	while(c>=48&&c<=57);

	return x;

}

const int P=998244353;

typedef long long ll;

int path[1<<16][16];

int cyc[1<<16],adj[16];

int n,m,msk;

int pw[17],coe[1<<16],sum[1<<16],f[16],res;

void inc(int &x,int v){if((x+=v)>=P) x-=P;}

void dec(int &x,int v){if((x-=v)<0) x+=P;}

int stk[1<<16],tp;

int main(){

	n=read();m=read();msk=(1<<n)-1;

	for(int i=0;i<m;++i){

		int u=read()-1,v=read()-1;

		adj[u]|=(1<<v);

		adj[v]|=(1<<u);

	}

	for(int i=0;i<n;++i) path[1<<i][i]=1;

	pw[0]=1;

	for(int i=1;i<=n;++i) inc(pw[i]=pw[i-1],pw[i-1]);

	for(int s=1;s<(1<<n);++s){

		int lb=__builtin_ctz(s);

		for(int i=lb;i<n;++i){

			if(!path[s][i]) continue;

			for(int j=lb+1;j<n;++j){

				if(s>>j&1) continue;

				if(adj[i]>>j&1) inc(path[s|(1<<j)][j],path[s][i]);

			}

		}

	}

	for(int s=1;s<(1<<n);++s){

		int lb=__builtin_ctz(s);

		for(int i=lb+1;i<n;++i)

			if(adj[i]>>lb&1) inc(cyc[s],path[s][i]);

		if(cyc[s]&1) cyc[s]+=P;

		cyc[s]>>=1;

		if(__builtin_popcount(s)<=2u) cyc[s]=0;

	}

	sum[0]=1;

	for(int s=0;s<(1<<n);++s){

		if(!cyc[s]) continue;

		int tt=(ll)pw[__builtin_popcount(s)]*cyc[s]%P;

		for(int i=0;i<n;++i)

			if(~s>>i&1)

			tt=(ll)(P+1-(f[i]=__builtin_popcount(adj[i]&s)))*tt%P;

		for(int dlt=msk^s;dlt;dlt=(dlt-1)&(msk^s)) stk[tp++]=dlt;

		while(tp){

			int dlt=stk[--tp],lb=__builtin_ctz(dlt);

			sum[dlt]=(ll)sum[dlt^(1<<lb)]*f[lb]%P;

			if(__builtin_parity(dlt)) inc(cyc[s|dlt],(ll)cyc[s]*sum[dlt]%P);

			else dec(cyc[s|dlt],(ll)cyc[s]*sum[dlt]%P);

		}

		inc(res,tt);

	}

	printf("%d\n",res);

	return 0;

}

给无向图定向

是zx2003 的做法。

众所周知内向基环树就是每个点出度都为 \(1\) 的弱联通图。计算无向图基环树我们有个方法：给无向图每一个点选择一条邻边定向为出边，考虑所有有向边形成了内向基环森林。

那么我们只需要对于每一个点子集导出子图计算度数的乘积，然后对集合幂级数求个 \(\ln\) 就可以得到一颗内向基环树。

有个小瑕疵，环长为 \(2\) 的内向基环树不能算在答案里。然而当我们把长度为 \(2\) 的环看成一条边，那么相当于在一个生成树上选一条边的方案数。用矩阵树定理计算即可。

时间复杂度为 \(O(2^nn^3)\)，瓶颈在对每个点子集计算矩阵树定理，感觉可能还能优化。

#include <cstdio>

#include <vector>

#include <algorithm>

#pragma GCC optimize(2,3,"Ofast")

#define FWTfor \

	for(int i=1;i<(1<<n);i<<=1) \

		for(int j=0;j<(1<<n);j+=(i<<1)) \

			for(int k=j;k<(j|i);++k)

using namespace std;

int read(){

	char c=getchar();int x=0;

	while(c<48||c>57) c=getchar();

	do x=(x<<1)+(x<<3)+(c^48),c=getchar();

	while(c>=48&&c<=57);

	return x;

}

const int P=998244353;

typedef long long ll;

int path[1<<16][16];

int cyc[1<<16],adj[16],pw[17],inv[17];

int n,m,msk;

void inc(int &x,int v){if((x+=v)>=P) x-=P;}

void dec(int &x,int v){if((x-=v)<0) x+=P;}

int f[17][1<<16],g[17][1<<16];

int ans[1<<16],res;

void FWT(int *arr){FWTfor inc(arr[k|i],arr[k]);}

void IFWT(int *arr){FWTfor dec(arr[k|i],arr[k]);}

int mat[17][17],len;

int qp(int a,int b=P-2){

	int res=1;

	while(b){

		if(b&1) res=(ll)res*a%P;

		b>>=1;a=(ll)a*a%P;

	}

	return res;

}

int det(){

	bool fl=0;

	int res=1;

	for(int i=1;i<=len;++i){

		int p=i;

		while(p<=len&&!mat[p][i]) ++p;

		if(p>len) return 0;

		if(p>i){

			for(int j=i;j<=len;++j) swap(mat[p][j],mat[i][j]);

			fl^=1;

		}

		res=(ll)res*mat[p][i]%P;

		int iv=qp(mat[p][i]);

		for(int j=i;j<=len;++j) mat[i][j]=(ll)mat[i][j]*iv%P;

		for(int j=i+1;j<=len;++j)

			for(int k=len;k>=i;--k)

				dec(mat[j][k],(ll)mat[j][i]*mat[i][k]%P);

	}

	if(fl) return P-res;

	return res;

}

int calc(int s){

	len=0;

	for(int i=0;i<n;++i)

		if(s>>i&1){

			++len;

			mat[len][len]=0;

			for(int j=0,t=0;j<n;++j)

				if(s>>j&1){

					++t;

					if(t!=len) mat[len][t]=0;

					if(adj[i]>>j&1){++mat[len][len];--mat[len][t];}

				}

		}

	for(int i=1;i<=len;++i)

		for(int j=1;j<=len;++j)

			if(mat[i][j]<0) mat[i][j]+=P;

	--len;

	return det();

}

int main(){

	n=read();m=read();msk=(1<<n)-1;

	for(int i=0;i<m;++i){

		int u=read()-1,v=read()-1;

		adj[u]|=(1<<v);

		adj[v]|=(1<<u);

	}

	for(int i=0;i<n;++i) path[1<<i][i]=1;

	inv[1]=pw[0]=1;

	for(int i=1;i<=n;++i) inc(pw[i]=pw[i-1],pw[i-1]);

	for(int i=2;i<=n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;

	for(int s=1;s<(1<<n);++s){

		int lb=__builtin_ctz(s);

		for(int i=lb;i<n;++i){

			if(!path[s][i]) continue;

			for(int j=lb+1;j<n;++j){

				if(s>>j&1) continue;

				if(adj[i]>>j&1) inc(path[s|(1<<j)][j],path[s][i]);

			}

		}

	}

	f[0][0]=1;

	for(int s=1;s<(1<<n);++s){

		int lb=__builtin_ctz(s),sz=__builtin_popcount(s);

		f[sz][s]=1;

		for(int i=0;i<n;++i)

			if(s>>i&1) f[sz][s]=(ll)__builtin_popcount(adj[i]&s)*f[sz][s]%P;

		for(int i=lb+1;i<n;++i)

			if(adj[i]>>lb&1) inc(cyc[s],path[s][i]);

		if(cyc[s]&1) cyc[s]+=P;

		cyc[s]>>=1;

		if(sz<=2) cyc[s]=0;

	}

	for(int i=0;i<=n;++i) FWT(f[i]);

	for(int i=1;i<=n;++i){

		for(int s=0;s<(1<<n);++s) g[i][s]=f[i][s];

		for(int s=0;s<(1<<n);++s){

			int tmp=0;

			for(int j=1;j<i;++j)

				inc(tmp,(ll)j*g[j][s]%P*f[i-j][s]%P);

			dec(g[i][s],(ll)inv[i]*tmp%P);

		}

	}

	for(int i=0;i<=n;++i) IFWT(g[i]);

	for(int s=1;s<(1<<n);++s){

		int sz=__builtin_popcount(s);

		int cur=g[sz][s];

		dec(cur,(ll)calc(s)*(sz-1)%P);

		cur=(ll)cur*pw[sz]%P;

		if(cur&1) cur+=P;

		cur>>=1;

		for(int i=0;i<n;++i)

			if(~s>>i&1) cur=(ll)cur*(P+1-__builtin_popcount(adj[i]&s))%P;

		inc(res,cur);

	}

	putchar('\n');

	printf("%d\n",res);

	return 0;

}

邪典做法

如果我们连 \(n\) 个点 \(n\) 条边的联通图是基环树都不知道，但是我们及其擅长集合幂级数与多项式。

那么我们就可以对于点集和边数设二元集合幂级数 \(F(x,y)=\sum f_{S,e} x^S y^e\)，对二元的占位幂级数求 \(\ln\) 就可以保证联通。

复杂度 \(O(2^nn^4)\)，不知是否可行，也不知能否通过。

[UR #14]人类补完计划的相关教程结束。