P8329 [ZJOI2022] 树 做题记录

九条可怜是一个喜欢树的女孩子，她想生成两棵均有 $n$ 个节点的树。

第一棵树的生成方式是：

1. 节点 $1$ 作为树的根。
2. 对于 $i \in [2, n]$，从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。

第二棵树的生成方式是：

1. 节点 $n$ 作为树的根。
2. 对于 $i \in [1, n - 1]$，从 $[i + 1, n]$ 中选取一个节点作为 $i$ 的父亲。

九条可怜希望对于任意 $i \in [1, n]$，若第一棵树中的节点 $i$ 为叶子，那么第二棵树中的节点 $i$ 为非叶子；若第一棵树中的节点 $i$ 为非叶子，那么第二棵树中的节点 $i$ 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。

九条可怜希望你统计生成两棵树的方案数是多少。具体地，你需要对于所有 $n \in [2, N]$ 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 $i$，两种方案中它的父亲不同。因为答案可能很大，你只需要输出答案对 $M$ 取模后的结果。

$2 \le N \le 500$，$10 \le M \le 2^{30}$。

设 $f(S)$ 表示叶子节点集合为 $S$ 时第一棵树的方案数，$g(T)$ 表示叶子节点集合为 $T$ 时第二棵树的方案数，那么有

$ans=\sum\limits_{S\cap T=\varnothing,S\cup T=\{1,2,3,\dots,n\}}f(S)g(T)$

发现非叶子节点非常难处理，所以不妨设 $f'(S)$ 表示非叶子节点集合为 $S$ 是第一棵树的方案树，设 $g’(T)$ 表示非叶子节点集合为 $T$ 时第二棵树的方案数，那么有

$\begin{aligned} ans&=\sum\limits_{S\cap T=\varnothing,S\cup T=\{1,2,3,\dots,n\}}f(S)g(T)\\ &=\sum\limits_{S\cap T=\varnothing,S\cup T=\{1,2,3,\dots,n\}}\sum\limits_{S'\in S,T'\in T}f'(S')g'(T')(-1)^{n-|S'|-|T'|}\\ &=\sum\limits_{S'\cap T'=\varnothing}f'(S')g'(T')(-1)^{n-|S'|-|T'|}2^{n-|S'|-|T'|}\,\,\,\text{（}S'\text{ 和 }T'\text{ 之外的节点可以出现在 }S\text{ 或 }T\text{ 中）}\\ &=\sum\limits_{S'\cap T'=\varnothing}f'(S')g'(T')(-2)^{n-|S'|-|T'|} \end{aligned}$

那么设 $dp_{i,j,k}$ 表示处理到 $i$，$|S'\cap\{1,2,3,\dots,i\}|=j,|T'\cap\{i+1,i+2,i+3,\dots,n\}|=k$ 时的 $f'(S')g'(T')(-2)^{n-|S'|-|T'|}$，有转移：

• $j\times k\times dp_{i,j,k}\to dp_{i+1,j+1,k}$
• $j\times k\times dp_{i,j,k}\to dp_{i+1,j,k-1}$
• $-2\times j\times k\times dp_{i,j,k}\to dp_{i+1,j,k}$

边界条件 $dp_{1,1,k}=1,1\le k\le n-1$。

答案为 $\sum\limits_{i=1}^{n-1}dp_{n-1,i,1}\times i$。

#include <iostream>
#include <cstdio>

using namespace std;

const int S=505;

int n,p;
int dp[S][S][S];

inline void addd(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n-1;i++) dp[1][1][i]=1;
	for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=i;j++)
		{
			for(int k=1;k<=n-i;k++)
			{
				addd(dp[i+1][j+1][k],1ll*j*k%p*dp[i][j][k]%p);
				addd(dp[i+1][j][k-1],1ll*j*k%p*dp[i][j][k]%p);
				addd(dp[i+1][j][k],p-2ll*j*k%p*dp[i][j][k]%p);
			}
		}
	}
	for(int i=2;i<=n;i++)
	{
		int ans=0;
		for(int j=1;j<=n-1;j++) addd(ans,1ll*dp[i-1][j][1]*j%p);
		printf("%d\n",ans);
	}
	return 0;
}