BZOJ4001 - Click Here
Description
Input
输入一个正整数N，代表有根树的结点数
Output
输出这棵树期望的叶子节点数。要求误差小于1e-9
Solutions
设$C_n$为卡特兰数，$F_n$为节点数为$n$的有根二叉树的叶子节点数之和。那么题目所求答案显然为$\frac{F_n}{C_n}$
那么现在的问题就是如何求出$F_n$
考虑枚举其中一棵子树的大小，那么有$F_n=2\sum_{i+j=n-1}F_iC_j$
分治FFT可以在$O(N \log^2 N)$内解决，显然不满足题目限制。
考虑求出$F_n$的通项公式。
设生成函数$f(x)=\sum F_ix^i , \ c(x) = \sum C_ix^i$
由卡特兰数的通项公式$C_n = \sum_{i+j=n-1}C_iC_j$可得$x \cdot c^2(x)+1=c(x)$
解得$c(x)=\frac{1 \pm \sqrt{1-4x}}{2x} = \frac{2}{1 \pm \sqrt{1-4x}}$
因为$\lim_{x \to 0^+} c(x)=1$，因此$c(x) = \frac{1 - \sqrt{1-4x}}{2x} = \frac{2}{1 + \sqrt{1-4x}}$
同理可得$f(x) = \frac{x}{1 - 2x \cdot c(x)} = \frac{x}{\sqrt{1 - 4x}}$
对$f(x)$展开有$f(x) = \frac{x}{\sqrt{1 - 4x}} = x \cdot (1 - 4x)^{-\frac{1}{2}} = \sum \dbinom{-\frac{1}{2}}{k} (-4)^k x^{k + 1}$
因为$\dbinom{-\frac{1}{2}}{k} = (-1)^k \dbinom{k - \frac{1}{2}}{k} = \frac{(-1)^k \dbinom{2k}{k}}{4^k}$，所以有$f(x) = \sum \dbinom{2k}{k} x^{k+1}$
即$F_n = \dbinom{2n-2}{n-1}$
因此最终答案为$\frac{F_n}{C_n} = \frac{n(n+1)}{2(2n-1)}$
此处对$\dbinom{k - \frac{1}{2}}{k} = \frac{\dbinom{2k}{k}}{4^k}$作出一些解释。
这个等式的证明运用到一个加倍公式的东西。关于这个公式更多的应用，可以翻阅《具体数学》第五章。
加倍公式即$r^\underline{k}(r - \frac{1}{2})^\underline{k}=\frac{(2r)^\underline{2k}}{2^{2k}}$，这个公式是十分显然的，只需要展开两边即可证明。
对该公式左右同时除以$(k!)^2$，则有$\dbinom{r}{k} \dbinom{r - \frac{1}{2}}{k} = \frac{\dbinom{2r}{k} \dbinom{2r-k}{k}}{4^k}$
令$r=k$，则可得到$\dbinom{r - \frac{1}{2}}{r} = \frac{\dbinom{2r}{r}}{4^r}$
CODE
CODE - Click Here