[TJOI2015]概率论[卡特兰数]

题意

\(n\) 个节点二叉树的叶子节点的期望个数。

\(n\leq 10^9\) .

分析

• 实际询问可以转化为 \(n\) 个点的不同形态的二叉树的叶子节点总数。

• 定义 \(f_n\) 表示 \(n\) 个节点的二叉树的个数， \(g_n\) 表示 \(n\) 个节点的不同形态的二叉树的叶子节点总数。

• 设一棵 \(n\) 个节点的树有 \(m\) 个叶子节点，每删去一个叶子节点都可以得到一棵大小为 \(n-1\) 的二叉树，考虑每个大小为 \(n-1\) 的二叉树，共有 \(n\) 个叶子节点，会被 \(n\) 棵大小为 \(n\) 的树考虑叶子贡献。

• 得到 \(g_n=\frac{n*f_{n-1}}{f_n}\)。

• \(f_n\) 是卡特兰数的第 \(n\) 项。

• 化简之后答案为\(\frac{n(n+1)}{4n-2}\) .

代码

#include<cstdio>
using namespace std;
double x;
int main(){
   scanf("%lf",&x);
   printf("%.9lf\n",(x*(x+1)/2/(2*x-1)));
   return 0;
}

[TJOI2015]概率论[卡特兰数]

原文：https://www.cnblogs.com/yqgAKIOI/p/9822306.html