营业日志 2020.12.25 求斯特林数的一些其他复杂度

· · 个人记录

大家圣诞节快乐……

我们认为以下几种问题及其复杂度在当下是已经基本普及的。

常规 行 S1

对于 0\le k\le n，计算所有 {n\brack k}。

理论基础：多项式平移（或称泰勒展开）

实现：约等于两次长为 n 的多项式乘法。\Theta(n\log n)

常规 行 S2

对于 0\le k\le n，计算所有 {n\brace k}。

理论基础：斯特林数的容斥公式

实现：一次长为 n 的多项式乘法。\Theta(n\log n)

常规 列 S1

对于 0\le k\le n，计算所有 {m+k\brack m}。

理论基础：EGF

实现：多项式快速幂。\Theta(n\log n)

常规 列 S2

对于 0\le k\le n，计算所有 {m+k\brace m}。

理论基础：EGF

实现：多项式快速幂。\Theta(n\log n)

常规 单点 S2

计算 {m\brace n}。

理论基础：斯特林数的容斥公式

实现：\Theta(n\log_n m)

行前缀 S2

对于 0\le k\le m，计算所有 {n\brace k}。

实现：\Theta(m\log_m n + m\log m)

这实际上就是对发现前缀只需要把朴素算法的卷积截短一点，没什么太多意思。

我们可以通过拉格朗日反演来算一些特殊位置的点值。

行后缀 S1

对于 0\le k\le n，计算所有 {m\brack m-k}。

我们使用拉格朗日反演公式。令 F(x) = \ln \frac 1{1-x}, G(x) = 1-\mathrm{e}^{-x}。由复合逆性质可得反演公式

\begin{aligned} m[x^m]F^{m-k}&=(m-k)[x^{-(m-k)}]G^{-m}\\ m[x^m]\left(\ln \frac 1{1-x}\right)^{m-k} &= (m-k)[x^k] \left(\frac x{1-\mathrm e^{-x}}\right)^m\\ {m\brack m-k} &= \frac{(m-1)!}{(m-k-1)!}[x^k] \left(\frac x{1-\mathrm e^{-x}}\right)^m \end{aligned}

行后缀 S2

我们令 F(x)=\mathrm e^x-1, G(x)=\ln (1+x)，可得

{m\brace m-k} = \frac{(m-1)!}{(m-k-1)!}[x^k] \left(\frac x{\ln(1+x)}\right)^m

因此二者都可以通过多项式快速幂在 \Theta(n\log n) 时间计算。

但是 行后缀 S1 还有常数更小的求法。

行后缀 S1

由于第一类斯特林数的一行有一个简单的表达方法，因此我们可以发现求后缀无非是求

\prod_{i=0}^m (1+ix)

的前 n 项，通过积和转换，对其取 \ln，我们只需要对每个 1\le k\le n，求出 k 次幂和。通过对伯努利数的预处理，这可以在常数较小的 \Theta(n\log n) 时间解决。

事实上，还有一些其他奇怪的复杂度。比如和模数是不大的质数 p 相关的系列。

小质数 单点 S1

计算 {m \brack n}。同余质数 p > m。

实现：\Theta(p)。

这一算法的要点在于注意到我们可以直接考虑行 OGF x^{\overline n} = x (x + 1) \cdots (x + n - 1) 在所有位置的点值可以通过前缀积优化复杂度计算出，之后通过计算单点的 IDFT 值做到严格线性。即

\operatorname{IDFT} [A]_j = \frac 1{p-1} \sum_k A_kg^{-jk}

小质数 远处 单点 S1

计算 {m \brack n}。同余质数 p。

实现：\Theta(p + \log_p m) + 进制转换。

注意到 x^{\overline p} \equiv x^p-x 和 Lucas 定理 f(x)^p \equiv f(x^p)，我们可以把计算需要的 m,n 降下来。

通过一点变体，我们可以以更小的常数计算第二类斯特林数的列。

改良 列 S2

对于 0\le k\le n，计算所有 {m+k\brace m}。

实现：\Theta(n\log m)。

我们可以发现它的 OGF 实际上就是 \frac1{(1-x)(1-2x) \cdots (1-mx)}，其中分母就是第一类斯特林数的带符号倒转。所以 \prod_{1\le k\le m} (1-kx) 是可以在 \Theta(m\log m) 时间内计算的。

接下来我们要注意到，对于 n 次多项式 f 商一个 m 次多项式 g，可以在 \Theta(n\log m) 时间内完成。我们可以每次 \Theta(m\log m) 求出这个商的前 m 项，设其为 h，那么考虑 f(x)/g(x)-h(x) 就只改变了前 m 项，而其 =(f(x)-g(x)h(x))/g(x)，其中分子的前 m 项为 0，我们就可以开始算下一组了。复杂度即为 \Theta((n/m) \cdot m\log m) = \Theta(n\log m)。

事实上，第一类斯特林数的一行前缀也是可以优化的。但注意到 {n \brack 1}=(n-1)!，所以目前的技术要带 \Omega(\sqrt n \log n) 了。

行前缀 S1

对于 0\le k\le m，计算所有 {n\brack k}。

实现：\Theta \left(\min \left\{m\sqrt n \log n, n\log n \right\}\right)。

先粗略分析指数。

考虑设大小 B，f_y(x) = \prod_{i=0}^{B-1} (x+y+i)，我们维护出 f_0,f_B,\dots,f_{(n/B) \cdot B} 关于 y 的点值表示。此时的多项式次数是 D=\min(B, m)，维护其的复杂度约为 \tilde O(D(B+n/B))。

接下来需要将它们都乘起来。

若 D=m，那么接下来无非是 \Theta(n/B) 回 m 次多项式乘法。复杂度为 \Theta(nm/B\log n)，总和前者，总共复杂度为 \tilde O(m(B + n/B))。由于此时 B\ge m，可在 m\le \sqrt n 时取到 \tilde O(m\sqrt n)，在 m>\sqrt n 时取到 \tilde O(m^2)。

若 D=B，那么接下来等价于 \Theta(n/m) 轮的 m 次多项式乘法，那已经消耗了 \tilde O(n) 的时间，而带回前面的复杂度也有 \tilde O(B^2+n)，因此不如朴素算法来的优！

可见，这种方法只有 m\le \sqrt n 的时候才是优秀的，注意到该方法在前面分块的部分可以通过经典的拉格朗日插值 + 倍增做到一个 \log，因此整个算法的复杂度为 \Theta(m\sqrt n \log n)。