题解 P6478 【[NOI Online #2 提高组]游戏（民间数据）】

· · 题解

恰好这个词看上去比较头疼，考虑大力容斥一下。

我们设 f(i) 表示存在 i 回合分出平局的方案数，g(i) 表示恰好 i 回合分出平局的方案数，显然有：

f(i)=\sum_{k=i}^m \binom{k}{i} g(k)

由二项式反演可知，

g(i)=\sum_{k=i}^m (-1)^{k-i} \binom{k}{i} f(k)

考虑把 f(i) 求出来。

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

有两种转移：


// Problem: P6478 [NOI Online #2 提高组]游戏（民间数据）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6478
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
#include <vector>
#define MOD 998244353
using namespace std;
vector<int> e[5005];
char s[5005];
int siz[5005],siz1[5005],n;
long long f[5005][5005],g[5005],fr[5005];
int c[5005][5005];
void dfs(int u,int fa)
{
 siz[u]=1,siz1[u]=(s[u]-'0');
 f[u][0]=1;
 for(auto v:e[u])
 {
  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<=min(siz[u],n/2);i++)//树形背包合并结果
   for(int j=0;j<=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=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()
{
 cin>>n;
 cin>>(s+1);
 fr[0]=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<=i;j++)
   c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
 for(int i=1;i<n;i++)
 {
  int u,v;
  cin>>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++)
 {
  long long 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;
  cout<<ans<<endl;
 }
 return 0;
}