题目链接

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}\),(对于另外一根\(\sqrt{1-4x}\)展开后每一项都是是负的,而卡特兰数不是,舍去) 对\(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=ng_{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; }

转载于:https://www.cnblogs.com/sssy/p/9367548.html