Description

问树大小为 (n)，每个节点的儿子个数 (le 3) 的本质不同树的个数。不考虑儿子之间的顺序。

(nle10^5)

Solution

因为这个题跟多项式关系比较大，所以就没有放到 Polya 定理学习笔记里面。

我们可以看出，假设我们设 (F(x)) 表示答案的普通型生成函数，那么，我们就有：

[F(x)=xfrac{F(x)^3+3F(x^2)F(x)+2F(x^3)}{6}+1 ]

个人觉得比较显然，直接拿 Polya 定理爆艹就行了。

问题就是怎么求这个东西，我们其实可以使用牛顿迭代法（分治 ( ext{FFT}) 应该也行，但是是 (log^2n) 的，所以就没有写）。

我们可以假设我们要求 (F(x)) 使得 (G(F(x))equiv 0pmod{x^n})，其中 (G(F(x))=xfrac{F(x)^3+3F(x^2)F(x)+2F(x^3)}{6}+1-F(x))。

然后就是牛顿迭代法标准套路了。假设已求出 (H(x)) 使得 (G(H(x))equiv 0pmod{x^{lceilfrac{n}{2} ceil}})，那么，我们就有：

[F(x)equiv H(x)-frac{G(H(x))}{G^{'}(H(x))}pmod{x^n} ]

问题就是如何求出 (G^{'}(H(x))) 了。主要是 (H(x^2)) 和 (H(x^3)) 怎么求导。

其实，因为我们现在已经知道 (H(x^2)) 和 (H(x^3)) 在 (pmod{x^n}) 的表达式了，所以，它们可以当常数，那么，

[G^{'}(H(x))=xfrac{3H(x)^2+3H(x^2)}{6}-1 ]

时间复杂度 (Theta(nlog n))，我的实现比较丑，所以不是很快。