题解 P3978 【[TJOI2015]概率论】

_rqy · 2018-06-02 18:51:51 · 题解

...这道题比楼下说的还要神奇——它不仅代码好写，证明也不用楼下说的那么麻烦。

首先，我们令f_n表示n个点的二叉树个数；g_n表示n个点的所有f_n棵二叉树的叶节点总数。

找规律第一步当然是打表啦~写个爆搜或者手算都可以。

我们发现一个规律：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_1=1。应该可以一眼看出来这是Catalan数列（其实一看那个1,2,5,14,42就应该知道，滑稽）

于是答案即为

代入卡特兰数的通项公式f_n=\frac{\binom{2n}{n}}{n+1}很容易就得到上式等于\frac{n(n+1)}{2(2n-1)}。

代码：

#include <cstdio>

int main() {
  double n;
  scanf("%lf", &n);
  printf("%.12f", n * (n + 1) / (2 * (2 * n - 1));
  return 0;
}