6132

· · 题解

思路

可以发现就是让你求限制度数的根向树森林，每条边带颜色的计数之和。

易知必有 0\in S，否则直接输出 0 即可。

考虑求出单颗树的 \rm EGF：

f=z\sum_{a\in S}{f^a\over a!}

故

z=\frac f{\sum_{a\in S}{f^a\over a!}}

即 f 的复合逆为

f^{(-1)}=\frac z{\sum_{a\in S}{z^a\over a!}}

然后答案即为

\sum_i[{z^n\over n!}]{k^{n-i}f^i\over i!}=k^n[{z^n\over n!}]\exp\frac fk

众所周知，有另类 Lagrange Inversion

[z^n]H(F)=[z^n]HG'\left(\frac zG\right)^{n+1}

但是这里求导不方便，不如直接用扩展 Lagrange Inversion

[z^n]H(F)=\frac1n[z^{n-1}]H'\left(\frac zG\right)^n

即

k^n[{z^n\over n!}]\exp\frac fk=k^{n-1}[{z^{n-1}\over(n-1)!}]\exp\frac zk\left(\sum_{a\in S}{z^a\over a!}\right)^n

于是即求

k^{n-1}[{z^{n-1}\over(n-1)!}]\exp\frac zk\left(\sum_{a\in S}{z^a\over a!}\right)^n

即

[{z^{n-1}\over(n-1)!}]\exp z\left(\sum_{a\in S}{(kz)^a\over a!}\right)^n

怎么求呢？

注意到 z^n 是 D-finite 的，\sum_{a\in S}{(kz)^a\over a!} 是代数的，所以 \left(\sum_{a\in S}{(kz)^a\over a!}\right)^n 是 D-finite 的！

具体的，设 F=\sum_{a\in S}{(kz)^a\over a!},G=F^n，则

FG'=nF'G

于是 G 可以整式递推。

总所周知 \exp z 也可以整式递推，所以 H=e^zG 也可以整式递推！

求完系数后还要乘一个 n!，这个也可以整式递推（快速阶乘算法，或者分段打表）。

当然，你也可以直接对 \Xi(e^zG) 求 ODE，然后上整式递推，也没有问题。

至此，我们得到一个 O(\sqrt n\log n) 的做法，其中 |S| 作为常数忽略不计。

Code

咕了。