题解 P3978 【[TJOI2015]概率论】
Nero_Claudius
2018-09-19 18:34:05
这道题。。。好像是第一道我自己切出来的黑题。。。
先说一句，牛顿二项式蒟蒻并不会，可以说是直接套结论。
求诸位老爷轻喷。
------------
这道题用**卡特兰数**搞。
卡特兰数这玩意从普及组初赛一路考到省选，十分有用。
如果不清楚这个概念的话可以看一下[这里](https://www.cnblogs.com/v-vip/p/8721098.html)。
卡特兰数是有两种计算方法：
1） 用递推算。
2） 用排列组合。
用它解题的流程一般是先说明所求的问题可以归到第一类中，然后再用第二类来计算具体的值。
像[这道题](https://www.luogu.org/problemnew/show/P1044)就可以用卡特兰数水过。
------------
我们假设$f_i$表示节点数为i的二叉树有多少种。
那么可以发现存在这样的关系：$f_i=\sum_{k=1}^{i-1}f_{k}f_{i-k-1}$。
这个东西满足卡特兰数的第一类表示方法。
所以运用第二类表示方法就可以得到$f_i=\frac{1}{n+1}C^n_{2n}$。
现在我们用$h_i$表示节点数为i的二叉树的叶子节点数量。
那根据$f_i$的值我们就可以得出递推式：$h_i=2\sum_{k=0}^{i-1}h_kf_{i-k-1}$
也就是$h_i=C^{i-1}_{2i-2}$
那么最终的答案就是$\frac{h_i}{f_i}=\frac{C^{i-1}_{2i-2}}{\frac{1}{n+1}C^n_{2n}}=\frac{n(n+1)}{2(2n-1)}$。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define qwq int
#define QAQ double
#define re register
using namespace std;
namespace Solve{
inline void read(qwq &x){
x=0;qwq f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
x*=f;
}
qwq n;
QAQ ans;
inline void solve(){
read(n);
ans=(QAQ)n*(QAQ)(n+1)/(QAQ)(2*n-1)/2;
printf("%.9lf",ans);
}
}
using namespace Solve;
qwq main(){
solve();
}
```