[记录] 生成函数习题
主要是学习生成函数怎么用，所以可能会省略此外的过程。
[YZOJ7198] 暴政之王
初始有一个 \(1,2,3\dots,n\) 的排列，再随机一个排列，将初始排列根据这个置换 \(m\) 次。
现在给出最终结果，问有多少排列可能是随机出的那个排列。
\(n\le 10^5,m\le10^9\)，模数为 \(10^9+7\)。
于是推出了一个这样的 DP 式子：
\[f(cnt,i)=\sum_{j=0}^{\lfloor\frac{i}{cnt}\rfloor}f(lst,i-j\cdot cnt)\cdot (\frac{l^{cnt-1}}{cnt})^j\cdot\frac{1}{j!} \]然后根据某常见生成函数的展开：
\[e^{Cx}=\sum_{n\ge 0}\dfrac{C^n}{n!}x^n \]可以回推出 DP 式子的封闭形式：
\[\begin{aligned} G_{cnt}(n)=e^{Cx^{cnt}}(C=\frac{l^{cnt-1}}{cnt}) \end{aligned} \]于是 DP 的过程相当于将若干 \(G_{cnt}\) 卷积，故最终的 \(G\) 可以表示为 \(e^{F(n)}\)
然后根据 \(O(n^2)\) 递推的方式展开 exp：
\[g(n)=\frac{1}{n}\sum_{i=1}^ni\cdot f(i)\cdot g(n-i) \]然后因为 \(F\) 的有效位置是 \(d(m)\) 个，所有求的 \(g\) 总共是 \(n\) 个位置，时间复杂度 \(O(n\cdot d(m))\)。
可能需要的结论：
一个长度为 \(k\) 的轮换，经过 \(m\) 次置换，分成 \(\gcd(k,m)\) 个长度为 \(\frac{k}{\gcd(k,m)}\) 的轮换。