【ZROI-21CSP7连测-Day1-T4】解谜

题意#

$n$ 个点，随机构成一颗有根树，求叶子的期望数量。

$n\leq 10^9$ .

对于 $20\%$ 的数据， $n\leq 20$ .

暴力是过不了的，应该有一些 DP 可以通过。

设 $f_i$ 表示包含 $i$ 个节点的有根树数量，那么根据卡特兰数公式，有 $f_n=\frac{1}{n+1}C_{2n}^{n}$ .

因此当 $n=20$ 时，不同的有根树数量为 $f_{20}=6564120420$ ，暴力无法通过 $\rm{Subtask}$ $1$ .

设 $g_i$ 表示有 $i$ 个节点的所有不同形态二叉树的叶子结点数量和，那么题目所求即为： $\frac{g_n}{f_n}$ .

先打表，至少可以打到 $n=10$ .

观察一下，可以发现一个规律：

g_n=f_{n-1}\cdot n

由 $f_n=\frac{1}{n+1}C_{2n}^{n}$ ，题目所求的答案可以用只含有 $n$ 的式子表示出来：

\operatorname{Ans} =\frac{g_n}{f_n} =\frac{f_{n-1}\cdot n}{f_n} =\frac{\frac{1}{n}\binom{2n-2}{n-1}\cdot n}{\frac{1}{n+1}\binom{2n}{n}} =\frac{(n+1)\cdot \frac{(2n-2)!}{(n-1)!(n-1)!}\cdot n}{n\cdot \frac{(2n)!}{(n)!(n)!}}

继续化简得到：

\operatorname{Ans}=\frac{(n+1)\cdot \frac{(2n-2)!}{(2n)!}}{\frac{(n-1)!(n-1)!}{(n)!(n)!}}=\frac{(n+1)\cdot \frac{1}{(2n-1)\cdot (2n)}}{\frac{1}{n^2}}=\frac{n\cdot (n+1)}{2\cdot (2n-1)}

用快速幂求逆元即可，时间复杂度为 $\mathcal{O}(\log p)$ ， $p$ 为模数.

下面给出 $g_n=f_{n-1}\cdot n$ 的证明。

对于每棵 $n$ 个点的二叉树，如果里面有 $k$ 个叶节点，那么我们分别把这 $k$ 个叶子删去，会得到 $k$ 棵 $n-1$ 个点的二叉树。

因此，所有 $n$ 个节点的二叉树中，每个叶子都唯一对应一棵 $n-1$ 个节点的二叉树。

对于每棵 $n-1$ 个点的二叉树，有 $n$ 个位置可以接上一个新的叶子节点。

因此，每棵 $n-1$ 个节点的二叉树都对应 $n$ 个叶子。（所有 $n$ 个节点的二叉树的所有叶子中的 $n$ 个）

综上，结论得证。