题解P8329 [ZJOI2022] 树

· · 题解

分析

设 f(S) 表示第一棵树的非叶子集合恰好为 S 时构造第一棵树的方案数。

设 g(T) 表示第二棵树的非叶子集合恰好为 T 时构造第二棵树的方案数。

那么答案为

Ans=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}f(S)g(T)

直接求这个不太好求，我们考虑容斥。

设 f'(S) 表示第一棵树的非叶子集合包含于 S 时构造第一棵树的方案数。

设 g'(T) 表示第二棵树的非叶子集合包含于 T 时构造第二棵树的方案数。

\begin{aligned} Ans&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}f(S)g(T)\\&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}\sum_{S'\subseteq S,T'\subseteq T}f'(S')g'(T')(-1)^{|S|-|S'|+|T|-|T'|} \\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-1)^{n-|S'|-|T'|}2^{n-|S'|-|T'|}\\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-2)^{n-|S'|-|T'|} \end{aligned}

其中倒数第二个等号的理由是：不属于 S' 和 T' 的那些元素可能在 S 中，也可能在 T 中。

然后可以 DP，我们设 dp_{i,j,k} 表示确定了 [1,i] 中的点在 S' 和 T' 中的情况，|\{1,\cdots,i\}\cap S'|=j，|\{i+1,\cdots,n\}\cap T'|=k ，且我们已经为 (1,i] 选好了第一棵树中的父亲，为 [1,i) 选好了第二棵树中的父亲时，这些父亲的方案数。

初值：\forall k\in[1,n)，dp_{1,1,k}=1。因为 1 一定是第一棵树的非叶子节点，也一定是第二棵树的叶子节点，不需要对其进行容斥。

转移时，分类讨论 i 在 S' 和 T' 中的情况，然后确定 i 在第一棵树中的父亲和 i-1 在第二棵树中的父亲：

  1. i$ 属于 $S'$，$dp_{i-1,j,k}$ 转移到 $dp_{i,j+1,k}$，系数为 $j\times k
  2. i$ 属于 $T'$，$dp_{i-1,j,k}$ 转移到 $dp_{i,j,k-1}$，系数为 $j\times k
  3. i$ 两个都不属于，$dp_{i-1,j,k}$ 转移到 $dp_{i,j,k}$，系数为 $-2\times j\times k

其中转移系数中包含 j\times k 的原因是：

考虑对于一个 S，如何计算 f'(S)。

对于节点 i\in(1,n]，fa_i 可能是 [1,i) 中的任意一个非叶子节点下面，那么方案数是 [1,i) 中非叶子节点的个数，也就是 j。

根据乘法原理，只需要将所有这样的点个数乘起来即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;ll mod;
ll dp[2][505][505];
int main(){
    scanf("%d%lld",&n,&mod);
    for(int i=1;i<n;i++)dp[1][1][i]=1;
    for(int i=2,now=0;i<=n;i++,now^=1){
        memset(dp[now],0,sizeof(dp[now]));
        ll ans=0;
        for(int j=1;j<i;j++)
            for(int k=1;k<=n-i+1;k++)if(dp[now^1][j][k]){
                dp[now][j][k]=(dp[now][j][k]+dp[now^1][j][k]*(mod-2)%mod*j%mod*k%mod)%mod;
                dp[now][j+1][k]=(dp[now][j+1][k]+dp[now^1][j][k]*j%mod*k%mod)%mod;
                dp[now][j][k-1]=(dp[now][j][k-1]+dp[now^1][j][k]*j%mod*k%mod)%mod;
                if(k==1)ans=(ans+dp[now^1][j][k]*j%mod*k%mod)%mod;
            }
        printf("%lld\n",ans);
    }
    return 0;
}