LOJ

分析

设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。

显然树上一定存在 $(1,2)$ 这条边，因此我们转移时讨论以 $2$ 为根的子树（记做 $A$）和整棵树其它部分（记做 $B$，显然它也是一棵树）的高度关系。

转移讨论一下整棵树最深的节点在哪里即可
$$
dp_{i,j}=\left(\sum_{k=1}^{i-2}\sum_{l=1}^{\min\{j-2,k\}}{i-2\choose k-1}dp_{k,l}dp_{i-k,j}\right)+\left(\sum_{k=1}^{i-1}\sum_{l=1}^{\min\{i-k,j\}}dp_{k,j-1}dp_{i-k,l}\right)
$$
边界为 $dp_{1,1}=dp_{1,2}=1$。

代码

偷懒把第一问打了个表 QAq

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int mod;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

const int N=24+10;

int n,dp[N][N],C[N][N];

int main() {
    n=read(),mod=read();
    if (n>=16) puts("6");
    else if (n>=10) puts("5");
    else if (n>=6) puts("4");
    else if (n>=3) puts("3");
    else printf("%d\n",n);
    for (int i=C[0][0]=1;i<=n;++i)
        for (int j=C[i][0]=1;j<=i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    dp[1][1]=dp[2][2]=1;
    for (int i=3;i<=n;++i)
        for (int j=2;j<=i;++j) {
            for (int k=1;k<=i-2;++k)
                for (int l=1;l<=min(j-2,k);++l)
                    dp[i][j]=(dp[i][j]+1ll*C[i-2][k-1]*dp[k][l]%mod*dp[i-k][j])%mod;
            for (int k=1;k<i;++k)
                for (int l=1;l<=min(i-k,j);++l)
                    dp[i][j]=(dp[i][j]+1ll*C[i-2][k-1]*dp[k][j-1]%mod*dp[i-k][l])%mod;
        }
    int ans=0;
    for (int i=1;i<=n;++i) ans=(ans+1ll*i*dp[n][i])%mod;
    for (int i=1;i<n;++i) ans=1ll*ans*qpow(i,mod-2)%mod;
    printf("%d\n",ans);
    return 0;
}