自动搬运

查看原文

来自洛谷，原作者为

	myee 与其诺诺以顺，不若谔谔以昌 | AFO

搬运于2025-08-24 22:17:44，当前版本为作者最后更新于2022-09-22 09:36:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

思路

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

易知必有 $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

咕了。