[NOI Online #2 提高组] 游戏

我们发现其实恰好并不太好做。
我们可以考虑大力容斥。
这个类型就很像二项式反演的做法

我们设(f(i))表示钦定(i)回合分出平局，其他位置不管的方案数，(g(i))表示恰好有(i)回合分出平局的方案数。
那么就有(f(n) = sum_{i = n}^minom{i}{n}g(i))
二项式反演一手则有
(g(n) = sum_{i = n}^m (-1) ^ {i - n}inom{i}{n}f(i))

那么我们只要考虑怎么求(f(i))即可。

那么我们考虑(f(i,j))表示以(i)为根的子树中，存在(j)对祖先-后代关系，且颜色不同。

有两种转移:
1.子树结果合并，树形背包。
2.根节点选择一个没选过的配对。

注意到我们(dp)时只固定了颜色不同的祖先-后代关系，其他的点应该直接自由组合。

#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long 
#define mod 998244353
#define MOD 998244353
#define N 5005

using std::min;

std::vector<int>e[5005];

char s[N];
int n;
ll fr[N];
ll c[N][N];
ll f[N][N],g[N];
int siz[N],siz1[N];
//
inline void dfs(int u,int fa){
//	std::cout<<u<<" "<<fa<<std::endl;
	siz[u] = 1,siz1[u] = (s[u] - '0');
	f[u][0] = 1;
	for(int i = 0;i < e[u].size();++i){
		int v = e[u][i];
		if(v == fa)continue;
		dfs(v,u);
		for(int i = 0;i <= siz[u] + siz[v];++i)
		g[i] = 0;
		for(int i = 0;i <= std::min(siz[u],n / 2);++i)
		for(int j = 0;j <= std::min(siz[v],n / 2 - i);++j)
		g[i + j] = (g[i + j] + f[u][i] * f[v][j]) % mod;
		for(int i = 0;i <= siz[u] + siz[v];++i)
		f[u][i] = g[i];
		siz[u] += siz[v],siz1[u] += siz1[v];
	}
	for(int i = std::min(siz1[u],siz[u] - siz1[u]);i;--i)
	if(s[u] == '1')
	f[u][i] = (f[u][i] + f[u][i - 1] * (siz[u] - siz1[u] - (i - 1))) % mod;
	else
	f[u][i] = (f[u][i] + f[u][i - 1] * (siz1[u] - (i - 1))) % mod;
}

int main(){
	scanf("%d",&n);
	fr[0] = 1;
	scanf("%s",s + 1);
	for(int i = 1;i <= n;++i)
	fr[i] = fr[i - 1] * i % mod,c[i][0] = 1;
	c[0][0] = 1;
	for(int i = 1;i <= n;++i)
	for(int j = 1;j <= n;++j)
	c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
	for(int i = 1;i < n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	for(int i = 0;i <= n / 2;++i)
	f[1][i] = f[1][i] * fr[n / 2 - i] % mod;
	for(int i = 0;i <= n / 2;++i){
		ll ans = 0;
		for(int j = i;j <= n / 2;++j)
		if((j - i) & 1)ans = (ans - c[j][i] * f[1][j] % mod + mod) % mod;
		else
		ans = (ans + c[j][i] * f[1][j]) % mod;
		std::cout<<ans<<std::endl;
	}
}