P6478 [NOI Online #2 提高组]游戏（树dp+广义容斥）

· · 题解

P6478 [NOI Online #2 提高组]游戏

“恰好”的方案数不好求，我们对这个问题进行转化：设 f_i 表示非平局回合数恰好为 i 的方案数， g_i 表示非平局回合数至少为 i 的方案数。根据二项式反演（广义容斥），

g_i=\sum_{j=i}^{m}\tbinom{j}{i}f_j\Rightarrow f_i=\sum_{j=i}^{m}(-1)^{j-i}\tbinom{j}{i}g_j

那么我们可以在 O(n^2 ) 的时间内把 g 转化为 f。接下来考虑如何求 g。

设 dp_{u,i} 表示在 u 子树内非平局回合数至少为 i （即选 i 对有“祖孙关系”的点对）的方案数。转移时，每遍历一棵子树就把答案并进去 dp_{u,j+k}=\sum_{v\in son_u}dp_{u,j}\times dp_{v,k}，然后再考虑 u 和其子树内一点配对的情况 。根据树形背包的复杂度分析，这个转移的复杂度是 O(n^2) 的。

求出 dp 数组后，有 g_i=dp_{1,k}\times(m-k)!，也就是在已选的 k 个点对以外，其他的自由组合。最后直接套二项式反演的式子求 f 即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace FGF
{
    int n,m;
    const int N=5005;
    const int mo=998244353;
    char s[N]; 
    struct edg{
        int to,nxt;
    }e[N<<1];
    int cnt,head[N],siz[N],sz[2][N],a[N];
    ll dp[N][N],tmp[N],fac[N],g[N],f[N],C[N][N];
    void add(int u,int v)
    {
        cnt++;
        e[cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
    }
    void dfs(int u,int fa)
    {
        siz[u]=1,sz[a[u]][u]=1,dp[u][0]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(v==fa)continue;
            dfs(v,u);
            for(int j=0;j<=min(siz[u]+siz[v],m);j++)tmp[j]=0;
            for(int j=0;j<=min(siz[u],m);j++)
                for(int k=0;k<=min(siz[v],m-j);k++)
                    tmp[j+k]=(tmp[j+k]+dp[u][j]*dp[v][k]%mo)%mo;
            siz[u]+=siz[v];
            sz[0][u]+=sz[0][v],sz[1][u]+=sz[1][v];
            for(int j=0;j<=min(siz[u],m);j++)dp[u][j]=tmp[j];
        }
        for(int i=sz[a[u]^1][u];i>=0;i--)
            dp[u][i+1]=(dp[u][i+1]+dp[u][i]*(sz[a[u]^1][u]-i)%mo)%mo;
    }
    void init()
    {
        for(int i=0;i<=n;i++)
        {
            C[i][0]=1;
            for(int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
        }
        fac[0]=1;
        for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mo;
    }
    void work()
    {
        scanf("%d",&n);m=n>>1;
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)a[i]=s[i]-'0';
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u); 
        }
        dfs(1,0);
        init();
        for(int i=0;i<=m;i++)g[i]=dp[1][i]*fac[m-i]%mo;
        for(int i=0;i<=m;i++)
            for(int j=i;j<=m;j++)
                if((j-i)&1)f[i]=(f[i]-C[j][i]*g[j]%mo+mo)%mo;
                    else f[i]=(f[i]+C[j][i]*g[j]%mo)%mo;        
        for(int i=0;i<=m;i++)
            printf("%lld\n",f[i]);
    }
}
int main()
{
    FGF::work();
    return 0;
}