不能根据代码量衡量题目难度系列……
# 题意
求 $n$ 个节点的形态不同的(无标号)二叉树的叶子节点数量的期望。
数据规模:$n\le 10^9$
# 解析
看到 $n$ 的规模,大概知道这是道结论题……下面来推一下结论:
从生成函数考虑,因为是无标号,应该是用普通生成函数。
设 $p_i$ 为 $i$ 个节点的二叉树的期望叶子数,那么就要求 $p_n$。再设 $c_i$ 表示 $i$ 个节点的二叉树的数量,显然有 $c_i=\sum_{j=0}^{i-1}c_jc_{i-1-j}$(枚举左右两棵子树的大小)。根据期望的线性性,可以像 DP 一样写出式子:
这个式子的意思就是讨论根的左右子树的大小,分别为 $j$ 和 $(i-j-1)$,那么概率为 $\frac{c_jc_{i-j-1}}{c_i}$,对期望的贡献为 $p_i+p_{i-j-1}$,于是 获得该贡献的概率×贡献 就是期望了。两边同时乘上 $c_i$:
观察到如果把括号展开,则有非常相似的 $c_xp_x$ 形式,于是令 $t_x=c_xp_x$。
可以看到第二个式子是卷积的形式,也就是:
写出这个式子过后,就可以想到生成函数了,设 $T(x),C(x)$ 分别为 $t,c$ 的生成函数:
> Hint
$2xT(x)C(x)$ 中 $T(x)C(x)$ 的第 $i$ 项表示根节点的两棵子树的大小为 $i$ 的方案数,整棵树则需加上根节点,即乘 $x$;
$+x$ 是考虑到只有根节点一个点的情况。
这个式子还可以进一步化简,因为 $C(x)$ 是可以写出式子的。观察递推式 $c_i=\sum_{j=0}^{i-1}c_jc_{i-1-j}$,敏锐的reader可以看出这是一个卡特兰数,可以直接背卡特兰数生成函数的结论,也可以现推(我背不着,所以推导一遍):
把 $C(x)$ 当未知数,其他(包括 $x$)当成常量。
然而我们知道卡特兰数不会有两个解,$\pm$ 一定会舍弃一个。考虑 $\lim_{x\to0}$,如果为 $+$:
(因为是一个大于 $1$ 的数除以无限接近 $0$ 的数)但是我们知道 $c_0=1$,所以 $\lim_{x\to0}C(x)=1$,矛盾。
所以应该取:顺便写出通项公式:
把 $C(x)$ 代入进去,然后解出 $T(x)$:
然后就是一些奇妙的操作……我也不知道为什么会这么想——把 $\left[xC(x)\right]$ 对 $x$ 求导:
可以发现 $[xC(x)]’=\frac{F(x)}x$。这意味着 $[xC(x)]’$ 和 $\frac{F(x)}x$ 对应项系数相等,即:
emm……真是妙极了
# 源代码
乍一看还以为是 ABC 的前几道水的数学题……
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
乱糟糟的感觉