P3978 [TJOI2015]概率论 做题记录

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

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

对于 $100\%$ 的数据，$1 \le n \le 10^9$。

对于每棵 $n$ 个点的二叉树，设它有 $k$ 个叶子，那么把这 $k$ 个叶子分别删去就能得到 $k$ 棵 $n-1$ 个点的二叉树。

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

由于 $n$ 个点的有根二叉树有 $\frac{\binom{2n}{n}}{n+1}$ 种，所以 $n$ 个点的所有二叉树总共有 $\binom{2n-2}{n-1}$ 个叶子，期望有 $\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;
}