bzoj4001: [TJOI2015]概率

生成函数 导数

---

题目链接

bzoj4001: [TJOI2015]概率论

题解

生成函数+求导
设$g(n)$表示有$n$个节点的二叉树的个数,$g(0) = 1$
设$f(x)$表示$n$个节点的二叉树叶子节点的个数，$f_0 = 0,f_1 = 1$
那么$ans = \frac{f_i}{g_i}$
对于$g_i$
考虑有一颗$n$个点的二叉树,由于左右字数都是二叉树,枚举左右子树的点数

$$g_n = \sum_{i = 0}^{n - 1}g_ig_{n - i - 1}$$
这就是卡特兰数，通项为$\frac{C_{2n}^{n}}{n + 1}$
对于$f_i$
枚举左右子树的大小，我们可以有$g$函数推出,由于左右对称，最后$*2$
$$f_n = 2\sum_{i = 0}^{n - 1}f_i*g_{n - i - 1}$$
我们要找到$f$与$h$的关系
另$G(x)$为$g$的生成函数，$F(x)$为$f$的生成函数
$$G(x) = x G^2(x) + 1,F(x) = 2xF(x)G(x) + x$$
对于$G(x)$他的封闭形式为$\frac{1-\sqrt{1-4x}}{2x}$,(对于另外一根不收敛,舍去)
对$F(x)$得到$F(x) = x * (1 - 4x)^{-\frac{1}{2}}$

$$(xG(x))'=\frac 1{\sqrt{1-4x}}=\frac{F(x)}x$$
$xG(x)$的每一项$xg_nx^n = g_nx^{n +1}$求导后变为$(n + 1)g_nx^n$,也就等于等式右边的$\frac{f_{n + 1}x^{n + 1}}{x} = f_{n + 1}x^n$ 也就是说$f_{n + 1} = (n+1)g_n$即$f_n=g_{n-1}$
带入$g_n =\frac{C_{2n}^{n}}{n + 1}$
化简得到
$$ans =\frac{n(n + 1)}{2(2n + 1)}$$

代码

#include<bits/stdc++.h> 
using namespace std; 
inline int read() { 
    int x = 0,f = 1; 
    char c = getchar(); 
    while(c < '0' || c > '9')c = getchar(); 
    while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar(); 
    return x * f; 
} 
const int maxn = 1000005;
const int INF = 0x7fffffff; 
int main() { 
    double n; 
    cin >> n; 
    printf("%.9lf\n",n * (n + 1.0) / (4 * n  -2)); 
    return 0; 
}