P8329 [ZJOI2022] 树 做题记录

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

第一棵树的生成方式是:

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

第二棵树的生成方式是:

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

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

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

2N5002 \le N \le 50010M23010 \le M \le 2^{30}

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

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

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

ans=ST=,ST={1,2,3,,n}f(S)g(T)=ST=,ST={1,2,3,,n}SS,TTf(S)g(T)(1)nST=ST=f(S)g(T)(1)nST2nSTS 和 T 之外的节点可以出现在 S 或 T 中)=ST=f(S)g(T)(2)nST\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}

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

  • j×k×dpi,j,kdpi+1,j+1,kj\times k\times dp_{i,j,k}\to dp_{i+1,j+1,k}
  • j×k×dpi,j,kdpi+1,j,k1j\times k\times dp_{i,j,k}\to dp_{i+1,j,k-1}
  • 2×j×k×dpi,j,kdpi+1,j,k-2\times j\times k\times dp_{i,j,k}\to dp_{i+1,j,k}

边界条件 dp1,1,k=1,1kn1dp_{1,1,k}=1,1\le k\le n-1

答案为 i=1n1dpn1,i,1×i\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;
}