题解 P5702 【调和级数求和】

· · 题解

这里给出一种简单的理解方式，使用 P5282 【模板】快速阶乘算法 中的算法稍加改写即可。认为在同余素数 p 意义下运算，下文省略了同余符号。

引用了很多 Min_25 博客中的公式，加了一些自己的解释，如有错误感谢指出！

矩阵描述

首先我们将阶乘使用矩阵表示如

\begin{bmatrix} n! \end{bmatrix} =\left( \prod _ {i=0}^{n-1} \begin{bmatrix}i+1\end{bmatrix} \right) \begin{bmatrix} 1 \end{bmatrix}

本题中记调和数 H_n=\sum _ {k=1}^n\frac{1}{k} 且 0\lt n\lt p 改写为矩阵有

\begin{bmatrix} (n+1)!\\(n+1)!H _ {n+1} \end{bmatrix}= \begin{bmatrix} n+1&0\\1&n+1 \end{bmatrix} \begin{bmatrix} n!\\n!H_n \end{bmatrix}

那么

\begin{bmatrix} {n+1\brack 1}\\{n+1\brack 2} \end{bmatrix}= \begin{bmatrix} n!\\n!H_n \end{bmatrix}= \left( \prod _ {i=0}^{n-1} \begin{bmatrix} i+1&0\\1&i+1 \end{bmatrix} \right) \begin{bmatrix} 1\\0 \end{bmatrix}

在这里 {n+1\brack 1} 和 {n+1\brack 2} 为第一类无符号斯特林数，本题某种意义上可以认为是求这两列斯特林数远处的某个点值。

注意乘法的大运算符都表示矩阵“左乘”，我们取 v=\left\lfloor \sqrt{n}\right\rfloor 并维护

\begin{aligned} \mathbf{M} _ d(x)&= \prod _ {i=1}^{d} \begin{bmatrix} x+i&0\\1&x+i \end{bmatrix}\\ &= \begin{bmatrix} g_d(x)&0\\h_d(x)&g_d(x) \end{bmatrix} \end{aligned}

的点值 \mathbf{M} _ d(0),\mathbf{M} _ d(v),\dots 即 g_d(x),h_d(x) 的点值 g_d(0),g_d(v),\dots 和 h_d(0),h_d(v),\dots ，而

\begin{aligned} \mathbf{M} _ {2d}(x)&= \mathbf{M} _ d(x+d)\mathbf{M} _ d(x)\\ &= \begin{bmatrix} g_d(x+d)&0\\h_d(x+d)&g_d(x+d) \end{bmatrix} \begin{bmatrix} g_d(x)&0\\h_d(x)&g_d(x) \end{bmatrix}\\ &= \begin{bmatrix} g_d(x)g_d(x+d)&0\\h_d(x+d)g_d(x)+g_d(x+d)h_d(x)&g_d(x)g_d(x+d) \end{bmatrix} \end{aligned}

已经导出了整个算法。在实际编写时使用 v=2^{\lceil \log_2(\sqrt{n})\rceil} ，最差的情况 v\approx 2\sqrt{n} 只是常数影响，此时不需要由 \mathbf{M} _ d(x) 的点值计算 \mathbf{M} _ {d+1}(x) 的点值，若希望计算 h _ d(x) 和 g _ d(x) 某 一个 点值而非平移点值，之前的拉格朗日插值公式也给出了一个经典的线性做法。

我们在求出 \mathbf{M} _ v(0),\mathbf{M} _ v(v),\dots 后有

\begin{bmatrix} (kv)!\\(kv)!H _ {kv} \end{bmatrix}= \begin{bmatrix} g_v(kv-v)&0\\h_v(kv-v)&g_v(kv-v) \end{bmatrix} \dots \begin{bmatrix} g_v(v)&0\\h_v(v)&g_v(v) \end{bmatrix} \begin{bmatrix} g_v(0)&0\\h_v(0)&g_v(0) \end{bmatrix} \begin{bmatrix} 1\\0 \end{bmatrix}

因为 v^2\geq n 所以令 kv\leq n 且 kv 尽可能大，那么剩余的项 n-kv=O(\sqrt n) 所以使用上述矩阵乘法模拟后求一次逆元即可，前面的点值的倍增与平移同 P5282 【模板】快速阶乘算法 中的一样为 O(\sqrt{n}\log n) 时间。

基本扩展

\begin{bmatrix} !n\\!(n+1) \end{bmatrix} =\left( \prod _ {i=0}^{n-1} \begin{bmatrix} 0&1\\i+1&i+1 \end{bmatrix} \right) \begin{bmatrix} 1\\0 \end{bmatrix}

其中 !n=n!\sum _ {k=0}^n\frac{(-1)^k}{k!} 是错位排列 n 个物品的方案数（即 \forall i 满足第 i 个物品不在第 i 个位置）。

\begin{bmatrix} !n\\(-1)^{n+1} \end{bmatrix} =\left( \prod _ {i=0}^{n-1} \begin{bmatrix} i+1&1\\0&-1 \end{bmatrix} \right) \begin{bmatrix} 1\\-1 \end{bmatrix} \begin{bmatrix} (n+1)!\\\sum _ {i=0}^ni! \end{bmatrix} =\left( \prod _ {i=0}^{n} \begin{bmatrix} i+1&0\\1&1 \end{bmatrix} \right) \begin{bmatrix} 1\\0 \end{bmatrix} \begin{aligned} \begin{bmatrix} \binom{n}{m+1}\\ \sum _ {i=0}^m\binom{n}{i} \end{bmatrix} &=\left( \prod _ {i=0}^{m} \begin{bmatrix} (n-i)/(i+1)&0\\1&1 \end{bmatrix} \right) \begin{bmatrix} 1\\0 \end{bmatrix}\\ &= \frac{1}{(m+1)!} \left( \prod _ {i=0}^{m} \begin{bmatrix} n-i&0\\i+1&i+1 \end{bmatrix} \right) \begin{bmatrix} 1\\0 \end{bmatrix} \end{aligned}

参考文献