• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

洛谷 P6478 – [NOI Online #2 提高组] 游戏(二项式反演+树形 dp)

开发技术 开发技术 2周前 (05-04) 6次浏览

题面传送门

没错这就是我 boom0 的那场 NOIOL 的 T3

一年前,我在 NOIOL #2 的赛场上折戟沉沙,一年后,我从倒下的地方爬起。

我成功了,我不再是从前那个我了

我们首先假设 A 拥有的点为 (p_1,p_2,cdots,p_m),B 拥有的点为 (q_1,q_2,cdots,q_m),显然 A、B 出牌的顺序是无关紧要的,因此我们不妨假设 A 就按 (p_1,p_2,cdots,p_m) 的顺序出牌,题目就等价于有多少个 (q) 的排列 (r) 满足恰好存在 (k)((p_i,r_i)) 是祖先关系。

其次,注意到这个“恰好”非常难受,因为它既包含匹配也包含不匹配的情况,而这两种情况是很难在一起考虑的。

这时候我们就可以很自然地想到一个套路叫“二项式反演”,我们考虑任意钦定 (k) 对必须匹配的点,即记 (f_k) 为钦定 (k) 对必须匹配的点,剩余随便排列的方案数,再记 (g_k) 为恰好存在 (k)((p_i,r_i)) 是祖先关系的方案数。那么有 (f_k=sumlimits_{i=k}dbinom{i}{k}g_i),反演以下即可 (g_k=sumlimits_{i=k}dbinom{i}{k}(-1)^{i-k}f_i)

接下来考虑怎样求 (f_i),这显然是一个简单的树形背包问题,设 (dp_{u,j}) 表示 (u) 的子树内钦定了 (j) 对要匹配的点的方案数。考虑转移,我们首先按照树形背包的套路将 (u) 所有子树的 (dp) 值合并起来,合并完之后的 (dp_{u,j}) 的显然就是在 (u) 所有儿子的子树中钦定 (j) 对需匹配的点的方案数,此时我们还需再考虑 (u) 的匹配情况,如果 (u) 属于 A,那么我们令 (dp_{u,j+1}leftarrow dp_{u,j}times(c1_u-j)),其中 (c1_u) 表示 (u) 子树内有多少个点属于 B,(u) 属于 B 的情况也同理,注意,这里的 (j) 需要倒序枚举。最终 (f_k=dp_{1,k}times(dfrac{n}{2}-k)!)

时间复杂度 (mathcal O(n^2))

总之当时觉得这道题是道 dlt,现在看来,也就 just so so 罢(

const int MAXN=5e3;
const int MOD=998244353;
char s[MAXN+5];
int n,c0[MAXN+5],c1[MAXN+5],dp[MAXN+5][MAXN+5];
int hd[MAXN+5],to[MAXN*2+10],nxt[MAXN*2+10],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int tmp[MAXN+5];
void dfs(int x,int f){
	dp[x][0]=1;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;dfs(y,x);
		memset(tmp,0,sizeof(tmp));
		for(int u=0;u<=min(c0[x],c1[x]);u++)
			for(int v=0;v<=min(c0[y],c1[y]);v++){
				tmp[u+v]=(tmp[u+v]+1ll*dp[x][u]*dp[y][v])%MOD;
			}
		c0[x]+=c0[y];c1[x]+=c1[y];
		for(int u=0;u<=min(c0[x],c1[x]);u++) dp[x][u]=tmp[u];
	}
	if(s[x]=='0'){
		for(int u=min(c0[x],c1[x]);~u;u--){
			dp[x][u+1]=(dp[x][u+1]+1ll*dp[x][u]*(c1[x]-u))%MOD;
		} c0[x]++;
	} else {
		for(int u=min(c0[x],c1[x]);~u;u--){
			dp[x][u+1]=(dp[x][u+1]+1ll*dp[x][u]*(c0[x]-u))%MOD;
		} c1[x]++;
	}
//	for(int u=0;u<=min(c0[x],c1[x]);u++) printf("%d %d %dn",x,u,dp[x][u]);
}
int fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
int f[MAXN+5],g[MAXN+5];
int main(){
	scanf("%d%s",&n,s+1);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	dfs(1,0);init_fac(n);
	for(int i=0;i<=n/2;i++) f[i]=1ll*fac[n/2-i]*dp[1][i]%MOD;
	for(int i=0;i<=n/2;i++){
		for(int j=i;j<=n/2;j++){
			if((j-i)&1) g[i]=(g[i]-1ll*binom(j,i)*f[j]%MOD+MOD)%MOD;
			else g[i]=(g[i]+1ll*binom(j,i)*f[j])%MOD;
		} printf("%dn",g[i]);
	}
	return 0;
}

喜欢 (0)