题目分析

题目要求计算随机生成的有根树的期望深度。树的构造规则是：除根节点外，每个节点的父亲在其之前的节点中均匀随机选择。核心思路是通过动态规划（DP）统计不同深度树的概率，进而计算期望。

解题思路

1. 状态定义：

   • f[i][j]：表示由 (i) 个节点构成的树深度恰好为 (j) 的方案数（模 (p)）。
   • g[i][j]：表示由 (i) 个节点构成的树深度恰好为 (j) 的概率（浮点数）。
   • s[i][j]：f[i][1] 到 f[i][j] 的前缀和（模 (p)）。
   • h[i][j]：g[i][1] 到 g[i][j] 的前缀和（浮点数）。

2. 状态转移：

   • 对于 (i) 个节点的树，最后一个节点的父亲可以是前 (i-1) 个节点中的任意一个。若前 (k) 个节点构成深度为 (j) 的树，剩余 (i-k) 个节点构成深度为 (j-1) 的树，则合并后深度为 (j)。
   • 概率转移需除以 (i-1)（父亲的选择数），方案数转移需取模。

3. 期望计算：

   • 遍历所有可能的深度 (j)，累加 (j \times \text{概率}(j)) 得到期望。

代码实现（带注释）

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
using ld = long double;

int n, mod;
int f[N][N], s[N][N];  // f[i][j]: i个节点深度为j的方案数；s[i][j]: f[i][1..j]的前缀和
ld g[N][N], h[N][N];   // g[i][j]: i个节点深度为j的概率；h[i][j]: g[i][1..j]的前缀和
int fc[N];             // 阶乘数组（未使用）

// 快速幂求逆元
int inv(int x) {
    int y = mod - 2, z = 1;
    while (y) {
        if (y & 1)
            z = 1ll * z * x % mod;
        y >>= 1;
        x = 1ll * x * x % mod;
    }
    return z;
}

int main() {
    scanf("%d%d", &n, &mod);
    fc[0] = 1;

    // 特判n=1的情况
    if (n == 1) {
        puts("1\n1");
        exit(0);
    }

    // 初始化阶乘（实际未使用）
    for (int i = 1; i <= n; i ++)
        fc[i] = 1ll * fc[i - 1] * i % mod;

    // 初始化：1个节点深度为1的方案数和概率均为1
    f[1][1] = 1, g[1][1] = 1;
    // 前缀和初始化
    for (int i = 1; i <= n; i ++)
        s[1][i] = 1, h[1][i] = 1;

    // 动态规划计算f和g
    for (int i = 2; i <= n; i ++) {
        for (int j = 2; j <= i; j ++) {
            ld cur = 0;  // 概率累加器
            int cnt = 0; // 方案数累加器

            // 枚举最后一个节点的父亲所在的子树大小k
            for (int k = 1; k < i; k ++) {
                // 情况1：前k个节点深度为j，剩余i-k个节点深度<=j-1
                cur += g[k][j] * h[i - k][j - 1];
                cnt = (cnt + 1ll * f[k][j] * s[i - k][j - 1] % mod) % mod;
                // 情况2：前k个节点深度<=j-1，剩余i-k个节点深度为j-1（合并后深度为j）
                cur += h[k][j - 1] * g[i - k][j - 1];
                cnt = (cnt + 1ll * s[k][j - 1] * f[i - k][j - 1] % mod) % mod;
            }

            // 除以i-1（父亲的选择数）得到概率和方案数
            cur /= (i - 1);
            cnt = 1ll * cnt * inv(i - 1) % mod;

            f[i][j] = cnt;
            g[i][j] = cur;
        }

        // 计算前缀和
        for (int j = 1; j <= n; j ++) {
            s[i][j] = (s[i][j - 1] + f[i][j]) % mod;
            h[i][j] = h[i][j - 1] + g[i][j];
        }
    }

    // 计算期望
    ld ans = 0.0;  // 浮点数期望
    int res = 0;   // 模意义下的期望

    for (int i = 2; i <= n; i ++) {
        res = (res + 1ll * f[n][i] * i % mod) % mod;
        ans += g[n][i] * i;
    }

    // 输出结果：四舍五入的整数和模p的值
    printf("%.0f\n%d\n", round(ans), res);
    return 0;
}

代码解释

1. 初始化：单个节点的树深度为1，方案数和概率均为1。
2. 状态转移：枚举最后一个节点的父亲位置，合并子树计算深度为 (j) 的方案数和概率。
3. 前缀和优化：使用前缀和减少重复计算，提高效率。
4. 期望计算：遍历所有深度，累加深度乘以对应概率得到期望，并分别输出四舍五入结果和模 (p) 结果。