[NOIOnline2提高组]游戏(二项式反演+树形背包).md
题面
略
分析
二项式反演的套路,设(f(i))为非平局回合数至少为(i)的情况. (g(i))为非平局回合数恰好为(i)的情况,则(f(i)=sum_{j=i}^m C_j^i g(j)).(这里的"至少"指的是我们"钦定"有(i)局一定平局,其他不一定,所以至少为(i).因此对(f(i))求后缀和不是(g(i)),会算重)我们要求的是(g(k)),但是(g)不太好求,考虑求(f)再反演得出(g).根据二项式反演定理(g(i)=sum_{j=i}^m C_{j}^i f(j))
(f)可以用树形背包来求。设(dp_{x,i})为(x)的子树内至少(i)对选择的有祖先-后代关系的点(即非平局的回合).那么(f(i)=dp_{1,i}cdot(m-i)!)(剩下的(m-i)对关系可以任意排序)
DP的时候先用模板的树形背包合并子树,然后考虑(x)这个点对答案的影响,有
(dp_{x,i} leftarrow dp_{x,i}+dp_{x,i-1}cdots( ext{x子树内不被x的拥有者拥有的节点个数}-(i-1)))
这是因为(x)可以和子树内不被(x)的拥有者拥有的,且还没被配对(减去(i-1))的节点形成非平局回合。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 998244353
#define maxn 5000
using namespace std;
typedef long long ll;
inline ll fast_pow(ll x,ll k){
ll ans=1;
while(k){
if(k&1) ans=ans*x%mod;
x=x*x%mod;
k>>=1;
}
return ans;
}
inline ll inv(ll x){
return fast_pow(x,mod-2);
}
ll fact[maxn+5],invfact[maxn+5];
void ini(int n){
fact[0]=1;
for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
invfact[n]=inv(fact[n]);
for(int i=n-1;i>=0;i--) invfact[i]=invfact[i+1]*(i+1)%mod;
}
ll C(int n,int m){
return fact[n]*invfact[n-m]%mod*invfact[m]%mod;
}
int m,n;
int a[maxn+5];
struct edge {
int from;
int to;
int next;
} E[maxn*2+5];
int head[maxn+5];
int esz=1;
void add_edge(int u,int v) {
esz++;
E[esz].from=u;
E[esz].to=v;
E[esz].next=head[u];
head[u]=esz;
}
int sz[maxn+5];
int cnt[maxn+5][2];
ll dp[maxn+5][maxn+5];//x的子树内,至少有i对祖先关系的方案数(有i对我们已经钦定,剩下的随便搞
//在dp转移中,我们钦定i对关系来转移,最后再乘上(m-i)!,表示剩下的关系可以任意匹配
//因为只是钦定,转移的时候就不需要考虑剩下的关系。而如果直接定义状态为恰好i对,转移时无法保证合法
void dfs(int x,int fa) {
static ll tmp[maxn+5];
sz[x]=1;
cnt[x][a[x]]++;
dp[x][0]=1;
for(int i=head[x];i;i=E[i].next){//先合并子树
int y=E[i].to;
if(y!=fa){
dfs(y,x);
for(int j=0;j<=sz[x]+sz[y];j++) tmp[j]=0;
for(int j=0;j<=sz[x];j++){
for(int k=0;k<=sz[y];k++){
tmp[j+k]=(tmp[j+k]+dp[x][j]*dp[y][k]%mod)%mod;
}
}
for(int j=0;j<=sz[x]+sz[y];j++) dp[x][j]=tmp[j];
sz[x]+=sz[y];
cnt[x][0]+=cnt[y][0];
cnt[x][1]+=cnt[y][1];
}
}
//计算x的贡献
for(int i=cnt[x][a[x]^1];i>=1;i--){//对于dp[x][i],x可以和子树里还没被选的与a[x]颜色相反的点匹配
//于是贡献为dp[x][i-1]*(cnt[x][a[x]^1]-(i-1)) 倒序是为了防止重复更新
dp[x][i]+=dp[x][i-1]*(cnt[x][a[x]^1]-(i-1))%mod;
dp[x][i]%=mod;
}
}
ll f[maxn+5],g[maxn+5];
int main() {
int u,v;
scanf("%d",&n);
m=n/2;
ini(n);
for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
for(int i=1;i<n;i++){
scanf("%d %d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(1,0);
for(int i=0;i<=m;i++) f[i]=dp[1][i]*fact[m-i]%mod;//求出真正的dp值
for(int i=0;i<=m;i++){
for(int j=i;j<=m;j++){
if((j-i)%2==1) g[i]-=C(j,i)*f[j]%mod;
else g[i]+=C(j,i)*f[j]%mod;
g[i]=(g[i]+mod)%mod;
}
printf("%lld
",g[i]);
}
}