E83 树上背包+二项式反演+排列组合 P6478 [NOI Online #2 提高组] 游戏

// 树上背包 O(n*m)
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read(){
  int x=0,f=1; char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
  return x*f;
}
const int N=5005,mod=998244353;
vector<int> e[N<<1];
int n,m,a[N],fac[N],inv[N],sz[N][2];
int f[N][N],t[N];

void dfs(int u,int fa){
  f[u][0]=1;
  sz[u][a[u]]=1;
  for(int v:e[u]){
    if(v==fa)continue;
    dfs(v,u);
    int Su=sz[u][0]+sz[u][1],Sv=sz[v][0]+sz[v][1];
    for(int i=0;i<=Su+Sv;i++)t[i]=f[u][i],f[u][i]=0;
    for(int i=0;i<=min(Su,m);i++)
      for(int j=0;j<=min(Sv,m-i);j++)
        f[u][i+j]=(f[u][i+j]+t[i]*f[v][j]%mod)%mod;
    sz[u][0]+=sz[v][0];
    sz[u][1]+=sz[v][1];
  }
  for(int i=sz[u][a[u]^1];i>=1;i--)
    f[u][i]=(f[u][i]+f[u][i-1]*(sz[u][a[u]^1]-(i-1))%mod)%mod;
}
int ksm(int a,int b){ //快速幂
  int r=1;
  for(;b;a=a*a%mod,b>>=1) if(b&1)r=r*a%mod;
  return r;
}
int C(int n,int m){ //组合数
  return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
  n=read();m=n/2;
  for(int i=1;i<=n;i++)scanf("%1d",&a[i]);
  for(int i=2;i<=n;i++){
    int u=read(),v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }
  fac[0]=inv[0]=1;
  for(int i=1;i<=m;i++)
    fac[i]=fac[i-1]*i%mod, //阶乘
    inv[i]=ksm(fac[i],mod-2); //逆元
  dfs(1,0);
  for(int k=0;k<=m;k++)
    f[1][k]=f[1][k]*fac[m-k]%mod;
  for(int k=0;k<=m;k++){
    int res=0;
    for(int i=k;i<=m;i++) //反演g[k]
      res=(res+((i-k&1)?mod-1:1)*C(i,k)%mod
                      *f[1][i]%mod)%mod;
    printf("%d\n",res);
  }
  return 0;
}

G48 二项式反演 G26 求组合数 快速幂 二项式反演学习笔记