> 科技资讯 > [UR #14]人类补完计划

[UR #14]人类补完计划

科技资讯 投稿 6300℃ 0 评论

[UR #14]人类补完计划

计数好题。

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

我们得到了 \(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\ 数组。

继续对叶子容斥

我们不妨设 \(f_{S,T}\ 表示点集为 \(S\，叶子点集为 \(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}\。

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

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

注意为了递推 \(\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=(llpw[__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]=(llsum[dlt^(1<<lb]*f[lb]%P;
			if(__builtin_parity(dlt inc(cyc[s|dlt],(llcyc[s]*sum[dlt]%P;
			else dec(cyc[s|dlt],(llcyc[s]*sum[dlt]%P;
		}
		inc(res,tt;
	}
	printf("%d\n",res;
	return 0;
}

给无向图定向

是zx2003 的做法。

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

时间复杂度为 \(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=(llres*a%P;
		b>>=1;a=(lla*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=(llres*mat[p][i]%P;
		int iv=qp(mat[p][i];
		for(int j=i;j<=len;++j mat[i][j]=(llmat[i][j]*iv%P;
		for(int j=i+1;j<=len;++j
			for(int k=len;k>=i;--k
				dec(mat[j][k],(llmat[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]=(llinv[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,(llj*g[j][s]%P*f[i-j][s]%P;
			dec(g[i][s],(llinv[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,(llcalc(s*(sz-1%P;
		cur=(llcur*pw[sz]%P;
		if(cur&1 cur+=P;
		cur>>=1;
		for(int i=0;i<n;++i
			if(~s>>i&1 cur=(llcur*(P+1-__builtin_popcount(adj[i]&s%P;
		inc(res,cur;
	}
	putchar('\n';
	printf("%d\n",res;
	return 0;
}

邪典做法

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

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

编程笔记 » [UR #14]人类补完计划

赞同 (35) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽