Description
.png)
.png)
Input
输入一个正整数N，代表有根树的结点数
Output
输出这棵树期望的叶子节点数。要求误差小于1e-9
Sample Input
1
Sample Output
1.000000000
HINT
1<=N<=10^9
题解
令$f_i$表示n个点无标号二叉树个数，那么枚举根的左子树的点数，可以得到
$$f_n = [n=0] + sum_{i = 0}^{n - 1} f_if_{n-i-1}$$
（一眼看过去就是卡特兰数，但是现在暂时用不到）
再令$g_i$表示n个点的无标号二叉树的叶节点数之和，则枚举左子树的点数，有
$$g_n = [n=1] + sum_{i = 0}^{n - 1} g_if_{n-i-1}$$
写出${f_i}, {g_i}$的生成函数的关系式，则有
$$F(x) = 1 + xF(x)^2$$
$$G(x) = x + xG(x)F(x)$$
解得
$$F(x) = frac{1-sqrt{1-4x}}{2x}$$
$$G(x) = frac{2x}{sqrt{1-4x}}$$
可以发现
$$frac{d}{dx}(xF(x)) = frac{dfrac{1-sqrt{1-4x}}2}{dx} = frac 12*4x*frac 1{sqrt{1-4x}} = frac 2{sqrt{1-4x}} = frac{G(x)}x$$
所以有$g_n = nf_{n-1}$，又因为$f_n = H_n$，所以
$$ans = frac{g_n}{f_n} = frac{H_{n-1}n}{H_n} = frac{n(n+1)}{2(2n-1)}$$
附代码（其实也没什么了）：
#include <algorithm>
#include <cstdio>
int main() {
double n;
scanf("%lf", &n);
printf("%.9lf", n * (n + 1) / 2 / (2 * n - 1));
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
