BZOJ4001 - [TJOI2015]概率论

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^k}$

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang