[bzoj 4001][TJOI2015] 概率论

Description

Input

输入一个正整数N,代表有根树的结点数

Output

 输出这棵树期望的叶子节点数。要求误差小于1e-9

Sample Input

1

Sample Output

1.000000000

HINT

 1<=N<=10^9

Solution

对于n个点的二叉树互不同构的方案数为\frac{1}{n+1}C_{2n}^{n},即Catalan数

f(i)表示n个点的二叉树叶子节点的个数

易知

f(i)=2\sum f(j)\times Catalan(n-j-1)

最后套个微积分差不多就能弄出一个结论:答案就是

\frac{n\times(n+1)}{2\times(2\times n+1)}

QQ图片20160808214649具体证明戳这里:我不是link

 

发表评论