「美团 CodeM 决赛」bt

简要题意：给定 $n,m$，对所有 $0\le k\le m$ 求 $$ \sum_{T\text{ is binary tree} , |T|=n}\sum_{u,v\in \operatorname{leaf}(T),u\le v} \operatorname{len}(u,v)^k $$ （其中 len 是节点数量） 设 $F,G,H$ 是树的数量，对祖先路径的统计，对全体路径的统计，得 $$\begin{cases} F = x(1+F)^2\\ G = x ( 1 + 2(1+F)G \mathrm{e}^t)\\ H = x ( \mathrm{e}^t + 2(1+F)H + G^2 \mathrm{e}^{3t}) \end{cases}$$ 简单代换，有 $$ H = \frac{x\mathrm{e}^t}{\sqrt{1-4x}} + \frac{x^3\mathrm{e}^{3t}}{\sqrt{1-4x} (1-\mathrm{e}^t\sqrt{1-4x})^2} $$ 暂作换元 $y=\mathrm{e}^t-1$，记 $\lambda=\sqrt{1-4x}$，有 $$ \begin{aligned} H &= x\mathrm{e}^t/\lambda + \frac{x^3(1+y)^3}{\lambda(1-(y+1)(1-\lambda))^2}\\ & = x\mathrm{e}^t/\lambda + \frac{x^3(1+y)^3}{\lambda^3(1-(1/\lambda - 1)y)^2} \end{aligned}$$ 而 $[x^n]\lambda^{-k}$ 很好计算。易得 $O(T+m^2)$ 的[代码实现](https://loj.ac/s/1295721)。同时易得 $O(\mathsf{M}(\sqrt T) + \mathsf{R}(m))$ 的理论复杂度。