洛谷3978 [TJOI2015]概率论

Luogu

BZOJ

算法

设 $g_n$ 表示 $n$ 个点的二叉树个数, $f_n$ 表示 $n$ 个点的二叉树的叶子数。

那么显然答案就是 $\frac{f_n}{g_n}$ 。

有一个显然的式子: $\large g_n=\sum\limits_{i=0}^{n-1}g_ig_{n-i-1}$ 。

可以理解为枚举左子树的大小。

还有一个显然的式子: $\large f_n=2\sum\limits_{i=0}^{n-1}g_if_{n-i-1}$ 。

还是可以理解为枚举左子树的大小,然后累加左边的叶子数乘右边的方案数。另外左右可以交换。

考虑用生成函数来求。设 $G(x)$ 为 $g$ 的生成函数, $F(x)$ 为 $f$ 的生成函数。

那么有 $G(x)=xG(x)^2+1$ , $F(x)=2xG(x)F(x)+x$ 。

解出 $G(x)=\frac{1-\sqrt{1-4x}}{2x}$ , $F(x)=\frac{x}{\sqrt{1-4x}}$ 。

可以发现, $(xG(x))'=\frac{1}{\sqrt{1-4x}}=\frac{F(x)}{x}$ 。

也就是说, $f_{n+1}=(n+1)g_n$ 即 $f_n=ng_{n-1}$ 。

然后可以发现 $g$ 为卡特兰数,那么把它的通项公式代入答案式中,得到 $ans=\frac{n(n+1)}{2n(n+1)}$ 。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

int main() {
    double n; scanf("%lf",&n);
    printf("%.9f\n",n*(n+1)/(2*(2*n-1)));
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 39 PM

发表评论