题解 P3830 【[SHOI2012]随机树】

· · 题解

P3830 [SHOI2012]随机树解题报告：

更好的阅读体验

题意

分析

期望神仙题。

第一问

我们考虑一次对深度为i的叶子结点的操作会造成什么影响——减少1个深度为i的叶子结点，增加两个深度为i+1的叶子结点，总贡献为i+2。

设f_i为i个叶子结点的情况下叶子结点平均深度的期望，那么有f_i=\frac{f_{i-1}\cdot (i-1)+f_{i-1}+2}{i}=f_{i-1}+\frac{2}{i}，解释一下，下面的i是叶子结点个数，上面左边的f_{i-1}\cdot (i-1)是原来i-1个叶子结点的总深度，f_{i-1}+2为新的叶子结点的贡献。

因为边界是f_1=0（根结点深度为0），因此答案为\sum_{i=2}^n\frac{2}{i}。

第二问

前置知识：正整数的期望公式，即对于正整数随机变量x，有E(x)=\sum_{i=1}^{\infty}P(x\geqslant i)

证明（须配合下方公式一同食用）：

第一步很显然是期望的定义，第二步是一个差分（因为x是正整数），第三步就是拆了一下式子，可以发现因为i趋近于无限，所以可以把求和挪过来一位，因此有了第四步（虽然没有可以挪到i=1的式子，但因为i=1时i-1=0，因此加上可以保持美观），最后相减就可以得到第五个式子了。

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-\sum_{i=1}^{\infty}P(x\geqslant i+1)\cdot i =\sum_{i=1}^{\infty}P(x\geqslant i)\cdot i-\sum_{i=1}^{\infty}P(x\geqslant i)\cdot(i-1) =\sum_{i=1}^{\infty}P(x\geqslant i)

设f_{i,j}为i个叶子结点的情况下，树深度大于等于j的概率，那么根据上面的正整数期望公式，我们的答案就是\sum_{i=1}^{n-1} f_{n,i}（因为根结点深度为0，因此不可能深度等于n），边界为f_{i,0}=1。

然后考虑如何求f_{i,j}，可以考虑枚举左子树的结点个数，得到f_{i,j}=\sum_{k=1}^{i-1} P(i,k)\cdot(f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}\cdot f_{i-k,j-1})。

解释：前面的P(i,k)表示在i个叶子结点的树中，左子树有k个叶子结点的概率；后面的f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}\cdot f_{i-k,j-1}利用了一种容斥的思想，即左子树深度大于等于j-1或右子树深度大于等于j-1的概率等于它们的概率之和减去它们的概率之积。

然后我们的问题到了怎么求P(i,k)，有一个非常神奇的结论：对于所有的k\in[1,i-1]，都有P(k)相等，即P(k)=\frac{1}{i-1}。

考虑如何证明，我们发现对左子树进行的操作是与右子树无关的，我们把所有操作分成扩展左子树和右子树，那么如果扩展了i-1次且左子树扩展了k-1次，那么右子树扩展了的k-i-1次一定与左子树无关（子树的根结点也需要进行一次扩展），因此我们需要用一个式子来表达选取这样的扩展方案的方案数：{(k-1)+(i-k-1)\choose k-1}={i-2\choose k-1}=\frac{(i-2)!}{(k-1)!(i-k-1)!}。

通过组合数我们知道了选定哪些操作，而这些操作作用在不同的结点上又是不一样的方案，因此我们还需要计算作用在不同结点上一共有多少种方案。对于左子树，第一次可以作用的结点数为1，第二次为2，第k-1为k-1，因此左子树方案数为(k-1)!，同理右子树的方案数为(i-k-1)!。

将选定操作的方案数和作用在不同结点上的方案数相乘就是左子树k个叶子结点，右子树i-k个叶子结点的方案：\frac{(i-2)!}{(k-1)!(i-k-1)!}\cdot (k-1)!\cdot (i-k-1)!=(i-2)!，它与k无关，因此所有的情况概率相等。又因为k的取值只有i-1种，所以P(k)=\frac{1}{i-1}。

故转移方程为f_{i,j}=\sum_{k=1}^{i-1}\frac{1}{i-1}\cdot(f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}\cdot f_{i-k,j-1})，答案为\sum_{i=1}^{n-1} f_{n,i}。

代码

#include<stdio.h>
const int maxn=105;
int q,n;
double ans;
double f[maxn][maxn];
int main(){
    scanf("%d%d",&q,&n);
    if(q==1)
        for(int i=2;i<=n;i++)
            ans+=2.0/i;
    if(q==2){
        for(int i=1;i<=n;i++){
            f[i][0]=1.0;
            for(int j=1;j<i;j++)
                for(int k=1;k<i;k++)
                    f[i][j]+=1.0/(i-1)*(f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1]);
        }
        for(int i=1;i<n;i++)
            ans+=f[n][i];
    }
    printf("%.6lf\n",ans);
    return 0;
}