给定 \(n\)，和一个 \(k\) 次多项式，对于每个 \(m\le n\)，设 \(\sigma\) 为一个大小为 \(m\) 且拆出的所有循环大小都为 \(3\) 的倍数的置换，\(|sp(\sigma)|\) 为它拆出的循环数，求所有 \(F(|sp(\sigma)|)\)，要求复杂度 \(\Theta(nk)\)
Sol：
机房大佬的神奇做法看不懂，只会题解的暴力推式子。
考虑把多项式写成牛顿级数（下降幂多项式的系数乘上一个 \(i!\)），实际上要求：
\[\sum_{\sigma} \sum_{i=0}^k b_i \binom{|sp(\sigma)|}{i}=\sum_{i=0}^k b_i \sum_{\sigma} \binom{|sp(\sigma)|}{i} \]这东西看着就像用生成函数做，后面实际上是对任意满足条件的置换中选出 \(i\) 个循环的方案数求和。
环排列的 EGF 为 \(\sum {x^i\over i}=-{ln 1-x}\)，为了满足 3 的倍数的限制，我们这样我们考虑套路单位根，可知 \(3\) 的倍数大小的循环的 EGF 为：
\[G=-{\ln (1-x)+\ln(1-\omega x)+\ln(1-\omega^2 x)\over 3} \]置换是由许多循环构成的，回忆 \(e^x\) 的泰勒展开，我们发现满足条件的置换的 EGF 为 \(F=e^{G(x)}\)，由于我们要对选出 \(i\) 个置换的方案数求和，引入新的变量 \(y\) 表示选或不选，则有 \(F=e^{(1+y)G}\)，从 \(p\) 阶满足条件的置换中选出 \(q\) 个循环的方案数为 \(p![x^py^q]F\)考虑两边对 \(x\) 求偏导：
\[{\delta F \over \delta x}=(1+y)G'F={1+y\over 3}({{1\over 1-x}+{\omega \over 1- \omega x}+{\omega^2 \over 1 - \omega^2 x}})F \]现在同时取 \([x^py^q]\) 项系数：
\[(p+1)[x^py^q]F={1\over 3}([x^py^q]({{1\over 1-x}+{\omega \over 1- \omega x}+{\omega^2 \over 1 - \omega^2 x}})F+[x^py^{q-1}]({{1\over 1-x}+{\omega \over 1- \omega x}+{\omega^2 \over 1 - \omega^2 x}})F) \]\[=\sum_{i=0}^p [x^i]({{1\over 1-x}+{\omega \over 1- \omega x}+{\omega^2 \over 1 - \omega^2 x}})\cdot ([x^{p-i}y^q]F+[x^{p-i}y^{q-1}]F) \]\[=\dfrac 13\sum_{i=0}^p\left(1+\omega^{i+1}+\omega^{2i+2}\right)\cdot\left([x^{p-i}y^q]F+[x^{p-i}y^{q-1}]F\right) \]考虑递推，不妨设 \(f_{p,q}=[x^py^q]F\)
\[(p+1)f_{p+1,q}=\dfrac 13\sum_{i=0}^p\left(1+\omega^{i+1}+\omega^{2i+2}\right)\cdot\left(f_{p-i,q}+f_{p-i,q-1}\right) \]\[=\dfrac 13\left(3(f_{p-2,q}+f_{p-2,q-1})+\sum\limits_{i=3}^p\left(1+\omega^{i+1}+\omega^{2i+2}\right)\cdot\left(f_{p-i,q}+f_{p-i,q-1}\right)\right) \]\[=\dfrac 13\left(3(f_{p-2,q}+f_{p-2,q-1})+\sum\limits_{i=0}^{p-3}\left(1+\omega^{i+1}+\omega^{2i+2}\right)\cdot\left(f_{p-3-i,q}+f_{p-3-i,q-1}\right)\right) \]\[=\dfrac 13\left(3(f_{p-2,q}+f_{p-2,q-1})+3(p-2)f_{p-2,q}\right) \]\[=f_{p-2,q-1}+(p-1)f_{p-2,q} \]\[f_{p,q}=\dfrac1pf_{p-3,q-1}+\dfrac{p-2}pf_{p-3,q} \]再令 \(g_{p,q}=p!f_{p,q}\)，则
\[g_{p,q}=p!\left(\dfrac1pf_{p-3,q-1}+\dfrac{p-2}pf_{p-3,q}\right) \]\[=(p-1)!f_{p-3,q-1}+(p-2)(p-1)!f_{p-3,q} \]\[=(p-1)(p-2)(p-3)!f_{p-3,q-1}+(p-1)(p-2)^2(p-3)!f_{p-3,q} \]\[=(p-1)(p-2)(g_{p-3,q-1}+(p-2)g_{p-3,q}) \]边界条件 \(g_{1,q}=g_{2,q}=0\)，\(g_{3,q}=2[q\le1]\)。\(O(nk)\) 递推即可
标签：钻石,right,dfrac,教练,联考,sum,omega,over,left From： https://www.cnblogs.com/wwlwakioi/p/16771667.html