第二类 Stirling 数模小质数的求算

· · 题解

众所周知：

F_k(x)=\sum_{n=k}^\infty \begin{Bmatrix} n \\ k\end{Bmatrix}x^n = x^k\left(\prod_{i=1}^k(1-ix) \right)^{-1}

把第二类 Stirling 数按定义递推展开，很容易可以得到上面的结果。

对于模数 p=2 的情况，连乘中只有 i 为奇数的项会保留下来，所以答案就是

[x^{n-k}]\frac{1}{(1-x)^{\lceil k/2 \rceil}}

用 Lucas 定理就可以简单地做到 \Theta(\log n)。

对于更一般的情况，要提取系数的 GF 变成了：

\prod_{i=1}^{p-1}\frac{1}{(1-ix)^{\left\lfloor \frac{k-i}{p} \right\rfloor+1}}

EI 哥哥告诉我们，要用根系关系的性质。因为质数 p 一定存在原根，就有

\prod_{i=0}^{p-1}(1-ix)\equiv\prod_{i=0}^{p-1}(1-\omega_{p-1}^ix)\equiv 1-x^{p-1}\pmod p

在化简的时候需要注意一下：如果 p 不整除 k，那么在 (1-x^{p-1})^{-1} 的若干次方外，总会多乘一小段。我们希望多出来的这段是多项式（只有有限项），所以化简为：

\frac{1}{(1-x^{p-1})^{\lfloor k/p \rfloor+1}}\prod_{i=k\bmod p+1}^{p-1}(1-ix)

把连乘展开，就得到 \mathcal O(p) 个分式提取系数再求和 —— 但这些中只有 1 项是非零的。提取分式的一项可以很容易做到 \Theta(\log_pn)，复杂度瓶颈在于快速提取那段连乘的一项系数。

[x^m]\prod_{i=d}^{p-1}(1-ix)=[x^{p-d-m}]\prod_{i=d}^{p-1}(x-i)=[x^{p-d-m}](x-d)^{\underline{p-d}}

又根据 EI 曾经提到过的做法，可以在 \Theta(p) 的时间复杂度内求出 (x-d)^{\underline{p-d}} 在 x\in[0,p-1] 处的整数点值（也就是进行了 DFT），随后再进行 IDFT 即可 \Theta(p) 求一项系数。

总时间复杂度就是 \Theta(p+\log_pn)，这个复杂度不仅与第一类 Stirling 数的求法一致，做法也是很类似的。