题解 P3978 【[TJOI2015]概率论】
_rqy
2018-06-02 18:51:51
...这道题比楼下说的还要神奇——它不仅代码好写，证明也不用楼下说的那么麻烦。
首先，我们令$f_n$表示$n$个点的二叉树个数；$g_n$表示$n$个点的所有$f_n$棵二叉树的叶节点总数。
找规律第一步当然是打表啦~写个爆搜或者手算都可以。
|n|1|2|3|4|5|...|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$f_n$|1|2|5|14|42|...|
|$g_n$|1|2|6|20|70|...|
我们发现一个规律：$g_n=nf_{n-1}$。
证明这个规律其实超级简单：
- 对于每棵$n$个点的二叉树，如果里面有$k$个叶节点，那么我们分别把这$k$个叶子删去会得到$k$棵$n-1$个点的二叉树；
- 而每棵$n-1$个点的二叉树恰好有$n$个位置可以悬挂一个新的叶子，所以每棵$n-1$个点的二叉树被得到了$n$次；
- 综上，我们即可得出结论：所有$n$个点的二叉树的叶子个数和等于$n-1$个点的二叉树个数$\times n$。
那么我们只需要求出$f$即可。而$f$的递推式可以通过枚举左子树结点个数得到：
$$f_n=\sum_{i=1}^{n-1}f_if_{n-i-1}$$
边界是$f_1=1$。应该可以一眼看出来这是Catalan数列（其实一看那个$1,2,5,14,42$就应该知道，滑稽）
于是答案即为
$$\frac{g_n}{f_n}=\frac{nf_{n-1}}{f_n}$$
代入卡特兰数的通项公式$f_n=\frac{\binom{2n}{n}}{n+1}$很容易就得到上式等于$\frac{n(n+1)}{2(2n-1)}$。
代码：
```cpp
#include <cstdio>
int main() {
double n;
scanf("%lf", &n);
printf("%.12f", n * (n + 1) / (2 * (2 * n - 1));
return 0;
}
```