Gtrimee

· · 题解

令 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 以内的 .