TopCoder13696 Morphling
前置知识：泰勒展开，符号化方法，无标号无根树计数
我们考虑我们目前序列为 \(a\)，然后从每个 \(i\to a_i\) 连边，得到一颗基环树。
我们考虑一次 \((x,y)\) 的影响，原本连向 \(x\) 的边连向了 \(y\)，原本连向 \(y\) 的边连向了 \(x\)，而 \(x,y\) 连向的边互换了，我们可以看成交换了 \(x,y\) 两个节点的编号。
那么我们实际上就要对入度小于等于 \(k\) 的无标号基环树森林计数。
我们把它分成三个部分环上每个点的子树，环的方案树，基环树森林。
首先我们考虑计数每个儿子个数不超过 \(k\)，根节点儿子个数不超过 \(k-1\) 的无根树计数。
我们考虑无标号无根树计数我们怎么做的，我们考虑设其生成函数为 \(F(z)\)，则我们得到：
\[F(z)=zMSET(F(z))= z\mathcal E(F(z)) \]而
\[\begin{aligned} MSET(F(z))&=\mathcal E(F(z))\\ &=\prod_{n\ge 0}\frac 1 {1-z^{\alpha_n}}\\ &=\prod_{n\ge 0}\frac 1 {(1-z^n)^{f_n}}\\ \ln \mathcal E(F(z))&=\sum_{n\ge 0}-f_n\ln(1-z^n)\\ &=\sum_{n\ge 0}f_n\sum_{j\ge 1}\frac {z^{jn}}j\\ &=\sum_{j\ge 0}\frac 1 j\sum_{n\ge 0}f_n(z^j)^n\\ &=\sum_{j\ge 0}\frac {F(z^j)}j\\ \mathcal E(F(z))&=\exp (\sum_{j\ge 0}\frac {F(z^j)}j) \end{aligned} \]然后我们考虑加入儿子个数的限制，我们增加一个元 \(y\)：
\[\begin{aligned} MSET(F(z))&=\prod_{n\ge 0}\frac 1 {1-z^{\alpha_n}y}\\ &=\prod_{n\ge 0}\frac 1 {(1-z^ny)^{f_n}} \end{aligned} \]首先这个似乎可以求偏导后递推，但是我们考虑另外一种做法。
我们考虑从小到大处理 \(f_i\)，每次知道 \(f_{1\sim i-1}\) 后我们能计算出 \(f_i\)。
然后我们考虑计算复杂度， \(z\) 次数不超过 \(n\)，\(y\) 度数不超过 \(k\)，然后我们可以暴力二维卷积，时间复杂度 \(O(nk\times \sum_{i=1}^n\frac n i)=O(n^2k\ln n)\)。
然后我们考虑得到一颗子树的生成函数后环上怎么做，我们发现就是一个 CYC 构造即可。
此时我们已经得到了一棵基环树的生成函数，我们考虑如何拓展到森林，由于 \(MSET(F)\) 的组合意义，我们知道，我们对得到的 \(F\) 进行欧拉变换就能得到最后的答案。
标签：4.13,frac,闲话,sum,ge,考虑,aligned,我们 From： https://www.cnblogs.com/Nityacke/p/18133228