闲话
?感觉没啥想说的诶
但是 jjdw 请勿宣称一些不存在的辈分关系 ????
再谈排列计数
和之前的社论没啥关系。
其实是对置换的环数计数得到的做法。
我们考虑一个环的 egf \(F(x)\),容易得到是
\]
然后做有标号 Set 构造,得到排列的 egf \(G(x)\) 是 \(\exp F(x)\)。
这使得我们可以轻易得到确定环数的排列,只需要对 \(yF(x)\) 做有标号 Set 构造再提取 \(y^k\) 系数即可。
下面是例题。
我们发现,题目中给的组合对象其实可以表示为 \(\exp (-\ln(1 - x) - x)\),这是由于组成部分里不能出现错排,把它减掉再构造即得。我们仍然无法解决原问题,但是我们可以对 \(\lvert\pi\rvert = m\) 与 \(k\) 快速求
\]
这是由于上面的组合意义是在 \(\text{cyc}(\pi)\) 里选 \(k\) 个,我们只需要决定每个环是否选择即可。而且这里只有排列长度,没有确定环数。这启发我们在环的 egf 里乘入 \((1 + y)\) 来得到选或不选的组合意义。
这样能得到答案即为
\]
我们不如将给定的多项式 \(F(x)\) 转化成形如
\]
的形式,随后就可以直接求出 \(F = e^{(1 + y)(-\ln(1-x)-x)}\) 的系数后代入了。转化形式本质上就是转下降幂形式,再乘一个阶乘。
随后我们要着眼于如何提取系数。这里复杂度可以支撑 \(O(nk)\),因此不妨考虑递推出系数。设 \(F[n, k] = [x^ny^k] F\)。
我们求 \(F\) 对 \(x\) 的偏导,也就是
\]
直接提取系数得到
\]
也就是
\]
可以做到 \(O(n k)\)。
我们其实没必要非得化成上面的二项式形式。我们首先作多点求值,然后其实只需要求出每种 \(\text{cyc}(\pi)\) 出现的次数,随后乘上点值即可。记得 egf 形式要乘 \(n!\),下面只提取 \(x^n\) 项系数。
承接上文的讨论,我们现在需要求的就是
\]
神奇形式。我们设 \(f(x)\) 由 \(f^2 / 2 = -\ln(1-x)-x\) 确定,容易看出它有复合逆,设是 \(g(x)\)。原式可化为 \(\exp (yf^2 / 2)\)。我们对原式作拉格朗日反演得到
\]
这个东西最后大略可以看出来是个直接提取的形式,我们只需要化简偏微分就行了。
\]
我们不妨观察 \(y^k\) 系数的形式,也就是提取
\]
\(1/n\) 可以最后和 \(n!\) 化简。下面只需要找到 \(g\) 的形式即可。
我们由
\]
代入 \(x = g\) 可以得到
\]
也就是
\]
作牛顿迭代即可。总时间复杂度 \(O(n \log n + k\log^2 k)\)。瓶颈在牛顿迭代