#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 510;
 
int n;          // 节点总数
LL P;         // 模数
LL dp[2][N][N];  // 滚动数组
// 处理到第 i 个节点时（now 表示当前滚动层），
// 前 i 个节点中有 j 个属于 S'（第一棵树非叶子集合大小）
// 后 n - i 个节点中有 k 个属于 T'（第二棵树非叶子集合大小）
// 并且已经为前 i 个节点在第一棵树中选好了父亲，为后 n - i + 1 个节点在第二棵树中选好了父亲
// 此时两棵树方案数的乘积
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> P;
    for (int i = 1; i < n; i ++) {
        dp[1][1][i] = 1;
    }
    
    // 从第 2 个节点开始处理，i 表示当前处理的节点编号
    // now 是当前层的索引（0 或 1），now ^ 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] == 0) {
                    continue;  // 跳过无效状态
                }
                
                LL val = dp[now ^ 1][j][k];
                LL t = j * k % P;  // 共同的系数：左边 j 个可选父亲 × 右边 k 个可选父亲
                
                // 情况1：节点 i 既不在 S' 也不在 T'
                // 对应容斥中的 (-2) 因子，所以要乘以 (mod - 2)
                // 状态保持 (j, k) 不变
                dp[now][j][k] = (dp[now][j][k] + val * (P - 2) % P * t) % P;
                
                // 情况2：节点 i 属于 S'（第一棵树的非叶子节点候选）
                // j 增加 1，k 不变
                // 系数为 j * k（左边 j 个可选父亲 × 右边 k 个可选父亲）
                dp[now][j + 1][k] = (dp[now][j + 1][k] + val * t) % P;
                
                // 情况3：节点 i 属于 T'（第二棵树的非叶子节点候选）
                // j 不变，k 减少 1（因为节点 i 从"未处理"变成"已处理"，且它属于 T'）
                // 系数为 j * k
                dp[now][j][k - 1] = (dp[now][j][k - 1] + val * t) % P;
                
                // 当 k == 1 时，表示右边只剩 1 个节点可能属于 T'
                // 这个状态可以贡献到答案中
                // 为什么？因为当 k == 1 时，右边的 T' 已经确定完了，可以累加进最终答案
                if(k == 1){
                    ans = (ans + val * t) % P;
                }
            }
        }
        cout << ans << "\n";
    }
    
    return 0;
}

#include <cstdio>
const int M = 505;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,MOD,f[M][M],g[M][M];
signed main()
{
    n=read();MOD=read();
    for(int i=0;i<=n;i++) f[0][i]=i+1;
    puts("1");
    for(int i=2;i<n;i++)
    {
        for(int j=0;j<=i;j++)
            for(int k=0;k<=n-i;k++)
                g[j][k]=f[j][k],f[j][k]=0;
        for(int j=0;j<=i;j++)
            for(int k=0;k<=n-i;k++)
            {
                int r=0;
                r+=(j+1)*(k+1)*g[j][k+1];
                r-=(j+1)*(k+1)*g[j][k];
                if(j) r+=j*(k+1)*g[j-1][k];
                r-=(j+1)*(k+1)*g[j][k];
                f[j][k]=(r%MOD+MOD)%MOD;
            }
        int ans=0;
        for(int j=0;j<=i;j++)
            ans=(ans+(j+1)*f[j][0])%MOD;
        printf("%lld\n",ans);
    }
}

分析

设 $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;
}