BZOJ-4001. [TJOI2015]概率论

题目要求出一个含有 n 个节点的有序二叉树的叶子节点的期望个数,n \leq 10^9,要求精确到 1.0 \times 10^{-9}

例如一个含有 3 个节点的二叉树,一共有 5 种情况,期望的叶子节点个数是 \frac{6}{5}

binary-tree-with-node3

首先可以用 H_n 表示有 n 个节点的二叉树的个数,空树没有节点,因此 H_0=1

考虑一棵有 n 个节点的二叉树,由于左右子树都是二叉树,可以枚举左右子树节点个数,因此可以得到递推式

 H_n = \sum_{i=0}^{n-1}H_i \cdot H_{n-i-1}

这也是著名的卡特兰数,它的通项是 \frac{1}{n+1}C_{2n}^n,等等会说怎么解

现在用 f_i 表示有 n 个节点的二叉树的叶子节点个数,这样最后期望就会是 \frac{f_i}{H_i}

首先可以知道 f_0=0, f_1=1,还是枚举子树大小,n 个节点的二叉树,左子树有 i 个节点,右子树一共有 H_{n-i-1} 种方案,这种情况答案就会增加 f_i\cdot H_{n-i-1},然后左右子树是对称的,最后还有乘 2,因此可以得到 f_n 的递推式

 f_n = 2\sum_{i=0}^{n-1} f_i \cdot H_{n-i-1}

现在设 H(x)H_n 的生成函数,F(x)f_n 的生成函数,观察到两个递推式基本相同,而且都是一个卷积的形式,卷积刚好对应生成函数的乘法,这样可以知道

 \begin{eqnarray*} H(x) &=& xH^2(x)+1 \\ F(x) &=& 2xF(x)H(x)+x \end{eqnarray*}

最后可以解出 H(x)F(x)

 \begin{eqnarray*} H(x) &=& \frac{1-\sqrt{1-4x}}{2x}\\ F(x) &=& \frac{x}{\sqrt{1-4x}} \end{eqnarray*}

注意到

 \int \frac{F(x)}{x}dx = -\frac{1}{2}\sqrt{1-4x}+C = xH(x)

这就说明只要求出 H(x),然后就很容易可以求出 F(x),现在考虑如何求 H(x),具体看 Catalan 数列及其应用

最后得出 H_n=\frac{1}{n+1}C_{2n}^n

 \begin{eqnarray*} xH(x) &=& \sum_{i=1}^\infty H_{i-1}x^i \\ \frac{d}{dx}xH(x) &=& \frac{1}{\sqrt{1-4 x}}\\ \sum_{i=0}^\infty (i+1)H_ix^i &=& \frac{F(x)}{x}\\ F(x)&=& \sum_{i=1}^\infty iH_{i-1}x^i \\ \end{eqnarray*}

因此 f_n=nH_{n-1},答案就是 \frac{nH_{n-1}}{H_n}=\frac{n(n+1)}{2(2n-1)}

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/04/bzoj-4001

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

8 thoughts on “BZOJ-4001. [TJOI2015]概率论

    1. 你把 \sqrt{1-4x} 展开后它的每一项值都是负数,在实际情况中 Catalan 数要是正数所以取了这个解,生成函数取哪个解是根据实际情况确定的

      其实还有一种方法就是你可以把 x = 1 带入试试看

  1. 请问一下,f(n) = 2\sum_{i=0}^{n-1} f(i)h(n-1-i)F(x)f(i)的生成函数的话,不应该是F(x) = 2xF(x)H(x)吗(虽然这样就无解了),不明白为啥泥会加x...

    1. 因为递推式的卷积范围是 0 \rightarrow n - 12F(x)H(x) 之后第 n 项对应的是 0 \rightarrow n 所以乘 x 右移,然后这样 x^1 这一项就消失了要补回来

      或者换一个方式直接想,2xH(x)F(x) 代表“根+左子树+右子树“组合起来的东西,但是在这里是认为根不是叶子节点,所以最后要补上根直接是叶子的情况

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.