(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} \]
其实也可以直接打表找规律