首先把给定的多项式转成牛顿级数，即转写成 F(x) = \sum\limits_{i=0}^{k-1} a_i \binom xi
然后套路的拆开项，考虑计算 \sum\limits_{\pi} \binom{ {\rm cyc}_{\pi} }{k}
让我们考虑一个错排，显然它是由非自环的循环置换为基本单位构成的，即 {\rm e}^{-x-\ln(1-x)}
然后考虑从中选 k 个。不难发现这只需要对一个循环置换附加一个因子 (1+y) 即可做到： {\rm e}^{(1+y)(-x-\ln(1-x))}
首先求考虑求 [x^n] {\rm e}^{y(-x-\ln(1-x))}，然后使用二项式展开并卷积处理。
设 \frac{f^2}2 = -x-\ln(1-x)，显然其存在复合逆，设复合逆为 g。
则
[x^n]{\rm e}^{yf^2/2} = \frac1n[x^{n-1}] \frac{ \partial{\rm e}^{yx^2/2} }{\partial x} \left(\frac xg\right)^n
我们知道 \frac{ \partial{\rm e}^{yx^2/2} }{\partial x} = xy {\rm e}^{yx^2/2} = \sum\limits_{i\ge 0} \frac{ x^{2i+1}y^{i+1} }{2^ii!}
因此 \frac1n[x^{n-1} y^k] \frac{ \partial{\rm e}^{yx^2/2} }{\partial x} \left(\frac xg\right)^n = \frac1{n2^{k-1} (k-1)!} [x^{n-2k}] \left(\frac xg\right)^n
考虑求 g。我们知道 \frac{f^2}2 = -x-\ln(1-x)
所以 \frac{x^2}2 = -g-\ln(1-g)
不幸的是如果我们直接对这个式子牛顿迭代，会出现一些意料之外的问题。
所以不妨将其改写成
\sqrt{-2g-2\ln(1-g)}-x=0
然后对其牛顿迭代。
时间复杂度 O(n \log^2 n)（视 n,k 同阶）。
代码：
1 |
|