【题解】[NOI Online #2 提高组] 游戏

$\rm LG6478\ [NOI\ Online\ {\tt \#}2$LG6478 [NOI Online #2 提高组$]$] 跑步

$\rm Description$Description

小 $\rm A$A 和小 $\rm B$B 正在玩一个游戏：有一棵包含 $n=2m$n=2m 个点的有根树（点从 $1\sim n$1∼n 编号），它的根是 $1$1 号点，初始时两人各拥有 $m$m 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点，若对手的点在自己的点的子树内，则该回合自己获胜；若自己的点在对方的点的子树内，该回合自己失败；其他情况视为平局。游戏共进行 $m$m 回合。

作为旁观者的你只想知道，在他们随机选点的情况下，第一次非平局回合出现时的回合数的期望值。

为了计算这个期望，你决定对于 $k=0,1,2,\cdots,m$k=0,1,2,⋯,m，计算出非平局回合数为 $k$k 的情况数。两种情况不同当且仅当存在一个小 $\rm A$A 拥有的点 $x$x，小 $\rm B$B 在 $x$x 被小 $\rm A$A 选择的那个回合所选择的点不同。

由于情况总数可能很大，你只需要输出答案对 $998244353$998244353 取模后的结果。

$\rm Solution$Solution

设 $f_{i,j}$fi,j​ 表示 $i$i 子树内，非平局对为 $j$j 对的方案数，有状态转移方程

$f_{i,j}=\sum_{k_1+k_2+\cdots+k_n=j}f_{{\rm son_1},k_1} \times f_{{\rm son_2},k_2} \times \cdots \times f_{{\rm son}_n,k_n}$fi,j​=k1​+k2​+⋯+kn​=j∑​fson1​,k1​​×fson2​,k2​​×⋯×fsonn​,kn​​

直接枚举显然不行，考虑每遍历一棵子树就把答案并进去，则有

$f_{i,j+k}=\sum_{v \in son_i}f_{v,j} \times f_{i,k}$fi,j+k​=v∈soni​∑​fv,j​×fi,k​

这个式子看起来是 ${\rm O}(n^3)$O(n3) 的，但是如果卡 $j,k$j,k 的上界就会变成 ${\rm O}(n^2)$O(n2)，证明为每个点 $(x,y)$(x,y) 只会对 ${\rm LCA}_{x,y}$LCAx,y​ 有一个复杂度的贡献。

最后的时候再把 $i$i 个贡献加进去，分别设 ${\rm A}_i,{\rm B}_i$Ai​,Bi​ 为 $i$i 子树内小 $\rm A/B$A/B 的节点个数，假设当前节点是小 $\rm A$A 的节点，那么就有
$f_{i,j}=f_{i,j}+f_{i,j+1} \times \max\big({\rm B}_i-j+1,0\big)$fi,j​=fi,j​+fi,j+1​×max(Bi​−j+1,0)

即之前有 $j-1$j−1 个非平局对，那么就会消耗掉 $j-1$j−1 个小 $\rm B$B 的节点，所以现在还剩 ${\rm B}_i-j+1$Bi​−j+1 个小 $\rm B$B 的节点可用。类似的，如果当前的节点是小 $\rm B$B 的节点就把上文的 ${\rm B}_i$Bi​ 换成 ${\rm A}_i$Ai​ 即可。

至此我们就可以在 ${\rm O}(n^2)$O(n2) 的时间复杂度内算出所有子树内选 $k$k 个非平局对的方案数。

我们先设 $g_k=f_{1,k} \times \bigg(\dfrac{n}{2}-k\bigg)!$gk​=f1,k​×(2n​−k)!，也就是说先固定选出来的 $k$k 个非平局对，然后把剩下的*组合。

但是这样会算重，因为*组合也可能贡献非平局对。我们设 $f_i$fi​ 表示恰好有 $i$i 个非平局对的方案数，可以发现对于每个 $f_i$fi​，它对 $g_k$gk​ 的贡献是 $\dbinom{i}{k} \times f_i$(ki​)×fi​，那么我们就有 $g_k=\sum\limits_{i=k}^m \dbinom{i}{k} \times f_i$gk​=i=k∑m​(ki​)×fi​。

这个可以二项式反演一下，有公式

$f_n=\sum^m_{i=n}\dbinom{i}{n} g_i \iff g_n=\sum^m_{i=n}(-1)^{i-n} \dbinom{i}{n} f_i$fn​=i=n∑m​(ni​)gi​⟺gn​=i=n∑m​(−1)i−n(ni​)fi​

套进去便得到了 $f_i$fi​。

$\rm Code$Code

#define int long long
#define mod 998244353
int n,x,y,num_edge,fac[5001],c[5001][5001],head[5001],f[5001][5001],g[5001],siz[5001],s[5001];
char str[5001];
struct EDGE {
	int v,next;
}E[10001];
void ADD_EDGE(int u,int v) {
	E[++num_edge].v=v;
	E[num_edge].next=head[u];
	head[u]=num_edge;
}
void DFS(int u,int fath) {
	siz[u]=1;
	s[u]=str[u]-'0';
	f[u][0]=1;
	for (int i=head[u];i;i=E[i].next)
		if (E[i].v!=fath) {
			DFS(E[i].v,u);
			for (int j=0;j<=siz[u]+siz[E[i].v];j++) g[j]=0;
			for (int j=0;j<=min(siz[u],n/2);j++)
				for (int k=0;k<=min(siz[E[i].v],n/2-j);k++)
					(g[j+k]+=f[u][j]*f[E[i].v][k]%mod)%=mod;
			for (int j=0;j<=siz[u]+siz[E[i].v];j++) f[u][j]=g[j];
			siz[u]+=siz[E[i].v];
			s[u]+=s[E[i].v];
		}
	for (int i=min(s[u],siz[u]-s[u]);i>=1;i--)
		if (str[u]=='1') (f[u][i]+=f[u][i-1]*(siz[u]-s[u]-i+1))%=mod;
		else (f[u][i]+=f[u][i-1]*(s[u]-i+1))%=mod;
}
signed main() {
	scanf("%lld%s",&n,str+1);
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	c[0][0]=1;
	for (int i=1;i<=n;i++) c[i][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	for (int i=1;i<n;i++) {
		scanf("%d%d",&x,&y);
		ADD_EDGE(x,y);
		ADD_EDGE(y,x);
	}
	DFS(1,0);
	for (int i=0;i<=n/2;i++) (f[1][i]*=fac[n/2-i])%=mod;
	for (int i=0;i<=n/2;i++) {
		int ans=0;
		for (int j=i;j<=n/2;j++)
			if ((j-i)&1) ((ans-=c[j][i]*f[1][j]%mod)+=mod)%=mod;
			else (ans+=c[j][i]*f[1][j]%mod)%=mod;
		printf("%lld\n",ans);
	}
	return 0;
}