题解 P3830 【[SHOI2012]随机树】

· · 题解

数学期望

背景

前人之述备矣，BJpers2神犇的证明更是极为精彩，让小萌新\varnothing深受触动。无奈\varnothing实在是太蒻了，只好属文以记之。

思路

设 g[i] 表示有 i 个叶子的二叉树的期望叶子平均深度。

则 i-1 个叶子的二叉树进行扩展后，叶节点数量变为 i，叶子深度之和增加2。

故有 g[i]=g[i-1]+2/i,g[1]=0。

即 \displaystyle\sum_{i=2}^n\displaystyle\frac{2}{i}.

将扩展过程表示为序列，则其中 “扩展左子树” 有 k-1 个，“扩展右子树” 有 i-k-1 个，序列的形式数量为：

\displaystyle \binom{k-1+i-k-1}{k-1}=\displaystyle\frac{(i-2)!}{(k-1)!(i-k-1)!}.

再考虑 k-1 次在左子树扩展形成的树的形态数，第 i 次可有 i 个叶节点可供扩展，故形态数为 (k-1)!。

同理，右子树的形态数有 (i-k-1)!。

故考虑扩展先后、树的形态，生成一个左子树有 k 个叶节点、右子树有 i-k 个叶节点的树的方案数为

\displaystyle\frac{(i-2)!}{(k-1)!(i-k-1)!} \cdot(k-1)!\cdot(i-k-1)!=(i-2)!

与 k 无关，即 P(k_1)=P(k_2)。

正整数随机变量 x 的期望值为：

E(x)=\sum_{i=1}^{\infty}P(x\geqslant i)

证明：

E(x)=\sum_{i=1}^{\infty}P(x=i)\cdot i=\sum_{i=1}^{\infty}(P(x\geqslant i)-P(x\geqslant i+1))\cdot i =\sum_{i=1}^{\infty}P(x\geqslant i)\cdot i-P(x\geqslant i)\cdot(i-1)=\sum_{i=1}^{\infty}P(x\geqslant i)

设 f[i][j] 为树有 i 个叶节点，深度不小于 j 的概率，考虑枚举左子树叶节点数量为 k，有

\displaystyle f[i][j]=\displaystyle\frac{1}{i-1}\sum_{k=1}^{i-1}f[k][j-1]+f[i-k][j-1]-f[k][j-1]\cdot f[i-k][j-1]

解释如下，首先考虑左、右子树深度不小于 j 的概率之和。再考虑左右子树深度皆大于等于 j 的情况计算了两次，减去一倍即可。

前文我们证明过，左子树叶节点数为 1,2,...,i-1 的概率相同，即均为 1/(i-1)。

初始条件，f[i][0]=1，因为无论有多少个叶子，深度大于等于 0 的概率总为 1。

由整数概率公式可知，期望深度 x 为：

E(x)=\sum_{i=1}^{\infty}P(x\geqslant i)=\sum_{i=1}^{n-1}f[n][i]\qquad(\forall x\geqslant n,P(x\geqslant i)=0).

代码

#include <cstdio>
int n, op;
double ans, f[105][105];
void solve1() {
    for(int i = 2; i <= n; ++i) ans += 2.0 / i;
}
void solve2() {
    for(int i = 1; i <= n; ++i) f[i][0] = 1;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            for(int k = 1; k < i; ++k)
                f[i][j] += (f[k][j-1] + f[i-k][j-1] - f[k][j-1]*f[i-k][j-1]) / (i-1);
    for(int i = 1; i < n; ++i) ans += f[n][i];
}
int main() {
    scanf("%d %d", &op, &n);
    if(op & 1) solve1();
    else solve2();
    printf("%.6lf\n", ans);
}

p.s

毕竟\varnothing还比较蒻嘛......有写错的地方请告诉她。

没有的话.......求赞【可怜】......