题解：P8329 [ZJOI2022] 树

王熙文 · 2024-10-10 13:29:55 · 题解

提供一种不需要容斥的做法。

思路

考虑枚举每个点是否是叶子结点，设 a_i=0 表示不是叶子，=1 表示是叶子。

对于一棵树，可以使用 dp 计算方案数。设 dp_{i,j} 表示前 i 个点有 j 个将来要接节点的节点。那么如果 a_j=0，dp_{i,j}=dp_{i-1,j} \cdot j + dp_{i-1,j-1} \cdot (j-1)，两个 dp 值分别表示当前节点的父亲不要/要继续接节点。a_j=1 也是一样，dp_{i,j}=dp_{i-1,j}\cdot j+dp_{i-1,j+1} \cdot (j+1)。对于另一棵树也是同理。

可以发现这个 dp 本质上计算的是：对于每个满足 b_0=b_n=0，若 a_i=0 则 b_i=b_{i-1} 或 b_{i-1}+1，若 a_i=1 则 b_i=b_{i-1} 或 b_{i-1}-1 的 b 序列，对 \prod\limits_{i=1}^{n-1} b_i 求和。

发现这个过程是可以倒推的，所以直接将这两棵树当前的 b 的值记录进状态即可。设 dp_{i,j,k} 表示考虑了前 i 个点，第一棵树的 b_i=j，第二棵树的 b_{i+1}=k。i+1 的原因是在第二棵树中加入 i 点决定的是 b_{i+1} 与 b_i 的关系。转移是简单的。

实现的时候可以将 j,k 可能的 8 种移动方式（a_i=0/1，两棵树分别从 i 还是 i\pm 1 转移）放到两个数组里。取模可以最后取，防止被卡常。

代码

#include<bits/stdc++.h>
using namespace std;
int dj[]={-1,-1,0,0,0,0,1,1};
int dk[]={-1,0,-1,0,0,1,0,1};
int n,mod;
long long dp[2][501][501];
int main()
{
    cin>>n>>mod;
    dp[0][0][0]=1;
    for(int i=1; i<=n; ++i)
    {
        memset(dp[i&1],0,sizeof(dp[i&1]));
        for(int j=0; j<=i; ++j)
        {
            for(int k=0; k<=n-i; ++k)
            {
                for(int l=0; l<8; ++l)
                {
                    int tj=j+dj[l],tk=k+dk[l];
                    if(tj<0 || tk<0) continue;
                    dp[i&1][j][k]+=dp[i-1&1][tj][tk]*(i==1?1:tj);
                }
                dp[i&1][j][k]=dp[i&1][j][k]*k%mod;
            }
        }
        if(i!=1)
        {
            int j=0,k=0; long long ans=0;
            for(int l=0; l<8; ++l)
            {
                int tj=j+dj[l],tk=k+dk[l];
                if(tj<0 || tk<0) continue;
                ans=(ans+dp[i-1&1][tj][tk]*tj)%mod;
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}