Loj#6538. 烷基计数 加强版 加强版

发表于 分类于 ， ， 阅读次数：

题意：求 个点的，儿子个数不超过 的无标号有根树个数。

答案对 取模，，时限 。

设为 ，则有 写出 的具体生成函数表示 ：

置换 的环大小集合为 。

置换 ， ， 的环大小集合为 。

置换 ， 的环大小集合为 。

于是

这能得到方程 :

可以化成半在线卷积，也可以牛顿迭代。

对于牛迭做法，相当于求

的零点。

在求出 之后， 其实都是已知的，可以（在求导中）当做常多项式来看待。

所以可求得

牛迭的倍增公式为