题目地址：洛谷：【P3830】[SHOI2012]随机树 – 洛谷

题目描述

题面来自洛谷。

输入输出格式

输入格式：
输入仅有一行，包含两个正整数 q, n，分别表示问题编号以及叶结点的个数。

输出格式：
输出仅有一行，包含一个实数 d，四舍五入精确到小数点后 6 位。如果 q = 1，则 d 表示叶结点平均深度的数学期望值；如果 q = 2，则 d 表示树深度的数学期望值。

输入输出样例

输入样例#1：

1 4

输出样例#1：

2.166667

输入样例#2：

2 4

输出样例#2：

2.666667

输入样例#3：

1 12

输出样例#3：

4.206421

输入样例#4：

2 12

输出样例#4：

5.916614

说明

2≤n≤100

题解

参考资料：[SHOI2012]随机树 – GuessYCB – 博客园
我们把两个子任务分开看。
第一个求叶节点平均深度的期望，我们令展开i次后这个值为dp[i]，则初值dp[1]=0，我们可以利用dp[i-1]来计算dp[i]，即将展开的那个叶子节点的深度为dp[i-1]，展开后变成了两个dp[i-1]+1深度的叶子，因此转移如下
\begin{aligned} dp[i] &= \frac{dp[i-1] \cdot (i-1) - dp[x-1] + 2(dp[x-1]+1)}{i} \\ &= dp[i-1] + \frac{2}{i} \end{aligned}
由于dp[i]只与dp[i-1]有关，我们甚至不用开数组。
第二个求树高的期望。期望的一种定义是所有情况的和除以情况数，跟展开的情况扯上关系是不好的，因为展开后的形态特别多，没法计算。我们其实并不在意树的形态，而在意树最终有几个儿子，考虑期望的另外一个定义\mathrm{E}(X) = \sum_i \mathrm{P}(X \geq i)，我们设计状态dp[i][j]表示有i个叶子的树深度不小于j的概率。转移的时候枚举左子树有多少个叶子，容斥原理计算即可
dp[i][j] = \frac{\sum_{k=1}^{x-1} (dp[k][j-1] + dp[i-k][j-1] - dp[k][j-1] \cdot dp[i-k][j-1])}{x-1}
初始值是dp[i][0]=1。答案就是\sum_{i=1}^{n-1} dp[n][i]。

代码

// Code by KSkun, 2018/4
#include <cstdio>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105;

int q, n;
double dp[MAXN][MAXN];

int main() {
    q = readint(); n = readint();
    if(q == 1) {
        double res = 0;
        for(int i = 2; i <= n; i++) {
            res += 2 / double(i);
        }
        printf("%.6lf", res);
    } else {
        for(int i = 1; i <= n; i++) dp[i][0] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                for(int k = 1; k < i; k++) {
                    dp[i][j] += dp[k][j - 1] + dp[i - k][j - 1] - dp[k][j - 1] 
                        * dp[i - k][j - 1];
                }
                dp[i][j] /= i - 1;
            }
        }
        double res = 0;
        for(int i = 1; i < n; i++) res += dp[n][i];
        printf("%.6lf", res);
    }
    return 0;
}