$玩具$玩具

求 $N$N 个结点的随机生成森林的 期望最高树高 .

$最初想法$最初想法

设 $F[i,j,k]$F[i,j,k] 表示高度为 $i$i, 使用 $j$j 个球, $k$k 个球在顶部的概率,

$F[i,j,k]=F[i,j-1,k]\ast \frac{j-3}{j-1}+F[i,j-1,k-1]\ast \frac{1}{j-1}+F[i-1,j-1,p]\ast \frac{1}{j-1}$F[i,j,k]=F[i,j−1,k]∗j−1j−3​+F[i,j−1,k−1]∗j−11​+F[i−1,j−1,p]∗j−11​

时间复杂度 $O\left(N^4\right)$O(N4), 没有 $De$De 出 $bug$bug, 暴力保底 $30pts$30pts .

$正解部分$正解部分

$题意:$题意: 起初只有一个根, 每次随机一个点加一个儿子, 求出最后形成的 $N$N 个节点的树的期望高度 .

$这里沿用原题解的几个定义\downarrow$这里沿用原题解的几个定义↓
说实话刚开始我觉得很迷 .

• $F[i,j]$F[i,j] 表示 $i$i 个点的森林, 有 $j$j 个点在第一颗子树的概率 .
• $f[i,j]$f[i,j] 表示有 $i$i 个节点的树, 深度不超过 $j$j 的概率 .
• $g[i,j]$g[i,j] 表示有 $i$i 个节点的森林, 深度不超过 $j$j 的概率 .

$F[i,j]$F[i,j] 很好转移:
$F[i,j]=F[i-1,j-1]\ast \frac{j-1}{i}+F[i-1,j]\ast \frac{i-j}{i}$F[i,j]=F[i−1,j−1]∗ij−1​+F[i−1,j]∗ii−j​

然后是 $g[i,j]$g[i,j] 的转移:
$g[i,j]=\sum _{k=1}^{i}F[i,k]\ast f[k,j]\ast g[i-k,j]$g[i,j]=k=1∑i​F[i,k]∗f[k,j]∗g[i−k,j]

意为在有 $i-k$i−k 个点的森林基础上生成一颗 $j$j 个点的树, 然后再取出其中满足条件的树 .

将若干深度不超过 $j-1$j−1 的树组成的森林 连上同一个根, 组成一个深度不超过 $j$j 的树, 即 $f[i,j]=g[i-1,j-1]$f[i,j]=g[i−1,j−1] .

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

typedef long long ll;
const int maxn = 305;

int N;
int mod;
int inv[maxn];
int F[maxn][maxn];
int g[maxn][maxn];
int f[maxn][maxn];

int main(){
        N = read(), mod = read();
        inv[1] = 1;
        for(reg int i = 2; i <= N; i ++) inv[i] = (((-1ll*mod/i*inv[mod%i])%mod)+mod)%mod;
        F[1][1] = 1;
        for(reg int i = 2; i <= N; i ++)
                for(reg int j = 1; j <= i; j ++){
                        int &t = F[i][j];
                        t = 1ll*F[i-1][j-1]*(j-1)%mod*inv[i]%mod;
                        t = (1ll*t + (1ll*F[i-1][j]*(i-j)%mod*inv[i]%mod)) % mod;
                }
        for(reg int i = 0; i <= N; i ++) g[0][i] = 1;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 0; j <= N; j ++){
                        f[i][j] = j?g[i-1][j-1]:(i<=1);
                        int &t = g[i][j];
                        for(reg int k = 1; k <= i; k ++)
                                t = (1ll*t + 1ll*f[k][j]*g[i-k][j]%mod*F[i][k]%mod)%mod;
                }
        int Ans = 0;
        for(reg int i = 1; i < N; i ++)
                Ans = (1ll*Ans + ((1ll*f[N][i]%mod - f[N][i-1]%mod)*i%mod)) % mod;
        Ans = (1ll*Ans%mod + mod) % mod;
        printf("%d\n", Ans);
        return 0;
}