等比数列求和的四种方法
litjohn
·
·
算法·理论
做到了 ABC448E，感觉很精妙。
题目中有个部分是模意义下等比数列求和。那么来讲讲它的几种做法。
公式
直接套公式。
\sum_{i=0}^n a^i = \frac{a^{n+1}-1}{a-1}
然后用逆元。不讲。
如果等比数列不是从 1 开始的，提取首项为公因数即可。下面所有讨论都默认 1 为首项。
更好的方法
公式法需要逆元，在逆元不存在时就寄了。而恰好，448E 的模数不是质数。
我们有几种方法来处理这个情况
下文定义
f(l, a) = \sum_{i = 0}^{l-1} a^i
分治求和
洛谷已经有篇文章讲过这种手法了。我在场上推出来也受到了它的启发。
大概来说，我们将序列平均分为两部分。
f(l, a) =
\begin{cases}
(1+a^{l/2})x, \; l \text{ is even}\\
x+a^{(l-1)/2}(ax+1), \; l \text{ is odd}
\end{cases}
其中 x := f(\lfloor \frac{l}{2} \rfloor, a)。
这样，做分治再套快速幂就可以以 2log 复杂度解决。不过这样不够优秀。
两种优化的分治
维护幂信息
注意到每层递归重算快速幂非常不优。我们在计算 f(l, a) 时顺便维护 a^l，在计算完 x 之后将 a^{\lfloor \frac{l}{2} \rfloor} 平方就得到 a^l。
复杂度单 log。
奇偶分拆
从中部分开不是非常优秀。考虑类似 FFT 的方法，把奇数和偶数位置拆开算。
f(l, a) =
\begin{cases}
(1+a)x, \; l \text{ is even}\\
a(1+a)x+1, \; l \text{ is odd}
\end{cases}
其中 x := f(\lfloor \frac{l}{2} \rfloor, a^2)。
同样复杂度 1log。
矩阵快速幂
注意到等比数列求和是一种常系数线性递推：
f(l, a) =
\begin{cases}
1, \; l=1\\
af(l-1,a)+1, \; \text{otherwise}
\end{cases}
于是自然可以矩阵快速幂维护。用 2 阶方阵作为转移矩阵。
T :=
\begin{bmatrix}
a & 1 \\
0 & 1
\end{bmatrix}
有
T \begin{bmatrix} x \\ 1 \end{bmatrix} = \begin{bmatrix} ax+1 \\ 1 \end{bmatrix}
于是：
T^{l-1} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} f(l, a) \\ 1 \end{bmatrix}
模数扩张
非常精妙的一种做法。
回想 448E 里我们用的另一个技巧。为了维护一个数除以另一个数下取整的值模 10007，我们推导出了这个式子：
\lfloor \frac{a}{b} \rfloor \bmod p = \lfloor \frac{a \bmod pb}{b} \rfloor \bmod p
回到最初的公式：
f(l, a) = \frac{a^l-1}{a-1}
那么：
\frac{a^l-1}{a-1} \bmod p = \frac{(a^l-1) \bmod p(a-1)}{a-1} \bmod p
只需要算一次快速幂即可。
注意特判 a = 1 的情况（和普通公式法一样）。