P3978 [TJOI2015]概率论 做题记录

为了提高智商,ZJY 开始学习概率论。有一天,她想到了这样一个问题:对于一棵随机生成的 nn 个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢?

判断两棵树是否同构的伪代码如下:

对于 100%100\% 的数据,1n1091 \le n \le 10^9

对于每棵 nn 个点的二叉树,设它有 kk 个叶子,那么把这 kk 个叶子分别删去就能得到 kkn1n-1 个点的二叉树。

由于每一颗 n1n-1 个点的二叉树都能悬挂 nn 个新的叶子,所以每一棵 n1n-1 个点的二叉树都会被上面的过程得到 nn 次。

由于 nn 个点的有根二叉树有 (2nn)n+1\frac{\binom{2n}{n}}{n+1} 种,所以 nn 个点的所有二叉树总共有 (2n2n1)\binom{2n-2}{n-1} 个叶子,期望有 (2n21n1)(2nn)n+1=(n+1)(2n2)!(n1)!2(2n)!n!2=(n+1)n22n(2n1)=n(n+1)2(2n1)\frac{\binom{2n-2}{1n-1}}{\frac{\binom{2n}{n}}{n+1}}=\frac{(n+1)\frac{(2n-2)!}{(n-1)!^2}}{\frac{(2n)!}{n!^2}}=\frac{(n+1)n^2}{2n(2n-1)}=\frac{n(n+1)}{2(2n-1)} 个叶子。

代码如下:

#include <iostream>
#include <cstdio>

using namespace std;

int n;

int main()
{
	scanf("%d",&n);
	printf("%.9Lf\n",n*(n+1)/(long double)(2*(2*n-1)));
	return 0;
}