(luogu3978)概率论

原题链接

思路:

首先, n个点组成的有根二叉树种数为:

$$c_n = \sum_{i=0}^{n-1} c_ic_{n-1-i}$$

即为卡特兰数.

令$e_n$为叶子节点的期望值, 由全期望公式, 有:

$$\begin{aligned} e_n & = \sum_{i=0}^{n-1}\frac{c_ic_{n-1-i}}{c_n}(e_i+e_{n-1-i})\\ & = \frac{2}{c_n}\sum_{i=0}^{n-1}c_ie_ic_{n-1-i} \end{aligned}$$

和式中每一项为左子树大小为$i$时的概率与对应的期望.

令$f_n=c_ne_n$, 有:

$$f_n = \sum_{i=0}^{n-1}f_ic_{n-1-i}$$

接下来便是多项式时间:

令$F(x) = \sum_{i}f_ix^i$, $C(x) = \sum_{i}c_ix^i$, 有:

$$\begin{aligned} F(x) & = x + 2\sum_{i=2}x^i\sum_{j=0}^{i-1}f_jc_{n-1-j}\\ & = x +2 xF(x)C(x)\\ \Longrightarrow F(x) & = \frac{x}{1-2xC(x)}\\ C(x) & = 1 + \sum_{i=1}x^i\sum_{j=0}^{i-1} c_jc_{n-1-j}\\ & = 1+xC^2(x)\\ \Longrightarrow \quad 0 & = xC^2(x) - C(x) + 1\\ \Longrightarrow C(x) & = \frac{1 \pm \sqrt{1-4x}}{2x} \end{aligned}$$

令$x=0$, 可得$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$, $F(x) = \frac{x}{\sqrt{1-4x}}$

接下来是重点: 探究$C(x)$与$F(x)$的关系:

$$\color{red}{(xC)' = \frac{1}{\sqrt{1-4x}} = \frac{F}{x}}$$

于是有:

$$\begin{aligned} \sum_{i=0}(i+1)c_ix^i & \equiv \sum_{i=0}f_{i+1}x^i\\ (i+1)c_i & = f_{i+1}\\ ic_{i-1} & = c_ie_i\\ e_i &= \frac{ic_{i-1}}{c_i} \end{aligned}$$

同时已知$c_i=\frac{2i \choose i}{i+1}$, 所以最终答案为:

$$e_i = \frac{i^2+i}{4i-2}$$

其实也可以直接打表找规律