自动搬运

查看原文

来自洛谷，原作者为

	Umbrella_Leaf 曹刘生子，当如孙仲谋。

搬运于2025-08-24 22:38:04，当前版本为作者最后更新于2022-05-06 21:17:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

分析

设 $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$。

$g'(T)$ 同理，只不过此时我们计算的是 $i-1$ 在第二棵树中的父亲方案数，也就是 $[i,n]$ 中非叶子节点的个数。

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

代码

#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;
}