玩具 [奇妙树形dp/计数]

$玩具$

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

---

$color{blue}{最初想法}$

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

$F[i, j, k] = F[i, j-1, k]* frac{j-3}{j-1} + F[i, j-1, k-1]*frac{1}{j-1}+F[i-1, j-1, p]*frac{1}{j-1}$

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

---

$color{red}{正解部分}$

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

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

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

$F[i, j]$ 很好转移:
$F[i, j] = F[i-1, j-1]*frac{j-1}{i} + F[i-1, j]*frac{i-j}{i}$

然后是 $g[i, j]$ 的转移:
$g[i,j]=sum_{k=1}^i F[i, k]*f[k, j] * g[i-k, j]$

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

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

---

$color{red}{实现部分}$

#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
", Ans);
        return 0;
}