P3830 [SHOI2012]随机树解题报告

解题报告

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

更好的阅读体验

题意

• 最开始给定一个根结点，然后进行$n-1$次操作，每次随机选定一个叶子结点给它添加一对左右子结点，求：
• 1.叶子结点平均深度的期望；
• 2.树深度的期望。
• 数据范围：$1\leqslant n\leqslant 100$。
• 注意：根结点深度为$0$。

分析

期望神仙题。

第一问

我们考虑一次对深度为$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)$
证明：

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

设$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;
}