自动搬运

查看原文

来自洛谷，原作者为

	jijidawang And in that light, I find deliverance.

搬运于2025-08-24 22:48:07，当前版本为作者最后更新于2023-02-28 14:47:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

令 $n$ 个点的满足题意的树的数量 $f_k(n)$ 的 OGF 为 $F_k(z)$，那么枚举根的最左侧子树大小即可得到递推：

$$f_k(n)=\sum_{i=0}^{n-1}f_{k-1}(i)f_k(n-1-i)$$

翻译为 OGF 就是卷积形式 $F_k(z)=1+zF_{k-1}(z)F_k(z)$，即

$$F_k(z)=\dfrac1{1-zF_{k-1}(z)}$$

通过类似的方法可以推得 $F_1(z)$ 的表达式，于是只需要解出递推 .

令 $p=998244353$ . 定义线性分式变换为函数 $f:\mathbb F_p[[z]]\to\mathbb F_p[[z]]$，满足存在 $a,b,c,d\in \mathbb F_p[[z]]$，使得

$$f(x)=\dfrac{ax+b}{cx+d}$$

那么可以发现线性分式变换对于复合是封闭的，具体可以验证：

$$\dfrac{a_0\frac{a_1x+b_1}{c_1x+d_1}+b_0}{c_0\frac{a_1x+b_1}{c_1x+d_1}+d_0}=\dfrac{(a_0a_1+b_0c_1)x+(a_0b_1+b_0d_1)}{(c_0a_1+d_0c_1)x+(c_0b_1+d_0d_1)} $$

观察递推，看成线性分式变换的形式就是 $a=0,\,b=1,\,c=1,\ d=-z$ . 令 $F_k(z)=\dfrac{a_kF_1(z)+b_k}{c_kF_1(z)+d_k}$，则可以简单写出系数的递推：

$$\begin{aligned}&a_i=c_{i-1}\\&b_i=d_{i-1}\\&c_i=c_{i-1}-z\cdot a_{i-1}\\&d_i=b_{i-1}-z\cdot d_{i-1}\end{aligned} $$

那么不难发现的是这个递推本质上可以看做二阶常系数齐次线性递推，于是大力解出 $a,b,c,d$ 后代入即可 .

于是可以通过多项式基本操作在 $\Theta(n\log n)$ 的时间复杂度内求出 $F_k(z)$ 的前 $n$ 项系数 . 前缀和后即为答案 . 时间复杂度为 $\Theta(n\log n+q)$，可以通过 . 如果实现优秀是可以跑到 500ms 以内的 .