数列求和
等比数列，即数列中相邻两数的比值相等。
因此不难发现，\(p^{a_1},p^{a_2},\ \dots\ ,p^{a_n}\) 也是等比数列。
那么，如何求上式之和呢？
题目
给定 3 个整数 \(a\), \(n\) 和 \(P\)，求 \(\sum_{i=1}^{n} a^i \mod P\) 的值。
\(\sum_{i=1}^{n} a^i \ \ =\ \ a^0 + a^1 + \dots + a^n\)，也就是一个等比数列。
\(a\) 一定不为 \(1\)。
暴力
暴力算法最容易想。此处给出两种代码。
\(\Theta (n\ logn)\)
int fpm(int a, int b, int p){
int res = 1;
while(b){
if(b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
int sum(int a, int n, int p){
int res = 0;
for(int i=0; i<=n; i++){
res = res + fpm(a, i, p) % p;
}
return res;
}
\(\Theta(n)\)
int sum(int a, int n, int p){
int res = 0;
int k = 1;
for(int i=0; i<=n; i++){
res = res + k % p;
k = k * a % p;
}
return res;
}
公式 \(\Theta(log^n)\)
若令 \(q\) 为公比，\(n\) 为项数，则等比数列求和公式为 :
推到可得，\(a^0 + a^1 + \dots + a^n\) 为：
该算法时间复杂度为 \(\Theta(log\ n)\)，是花在了求次幂上。当然，若能提前处理好次幂表，复杂度将会降为 \(\Theta(1)\)。
在此提醒，该算法有着极大的缺陷。在求除法时，直接取模将会存在危险。可以使用扩展欧几里得算法求出逆元后求解。
秦九韶(\(sh\acute{a}o\))算法 \(\Theta(n)\)
观察以下几组数列：
- \(a^0\)
- \(a^1 + a^0\)
- \(a^2 + a^1 + a^0\)
- \(a^3 + a^2 + a^1 + a^0\)
\(\ \ \ \ \ \ \vdots\)
\(\ n.\ a^n + a^{n-1} + a^{n-2} + \dots + a^1 + a^0\)
如果你仔细观察，你会惊奇的发现的 \(x\) 行的数列之和为 \(x-1\) 行的 \(a\) 倍还要多1(即 \(a^0\))。
具体如下：
\((a^{n-1} + a^{n-2} + \dots + a^1 + a^0) \times a + 1\)
\(=a^{n-1}\times a + a^{n-2}\times a + \dots + a^1\times a + a^0\times a + 1\)
\(=a^n + a^{n-1} + a^{n-2} + \dots + a^1 + 1\)
因此，若令 \(f_i\) 为 \(\sum_{j=0}^{i} a^j \mod P\) 的值，就可以得到等比数列的动态转移方程: \(f_i = f_{i-1}\times a + 1\) 。
int f[N];
int sum(int a, int n, int p){
f[0] = 1;
for(int i=1; i<=n; i++){
f[i] = (f[i-1] * a + 1) % p;
}
return f[n];
}
或者化简得:
int sum(int a, int n, int p){
int res = 1;
while(n--){
res = res * a + 1;
res %= p;
}
return res;
}
一般的，上面三种就够了。。。
分治 \(\Theta((log^n)^2)\) AT 题目链接
为了一致，我们将题目中的 \(A\) 改为 \(a\)，\(X\) 改为 \(n\)，\(M\) 改为 \(P\)。
ABC293E 这道题中，\(n\) 的范围达到了恐怖的 \(10^{12}\)，因此我们换一种思路来思考文章开头的问题。
我们举一个实际的例子:
\(a = 2,\ n = 7\)
\(2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6=\ ?\)
根据分治的思想，我们可以将问题化成多个子问题。
不妨将上列数字分成 \(3\) 组：
| 第 \(1\) 组: \(2^0,\ 2^1,\ 2^2\)
| 第 \(2\) 组: \(2^3,\ 2^4,\ 2^5\)
| 第 \(3\) 组: \(2^6\)
第 \(1\) 组为前 \(\lfloor \dfrac{n}{2} \rfloor\) 个数。
第 \(2\) 组为第 \(1\) 组数后面 \(\lfloor \dfrac{n}{2} \rfloor\) 个数。
若分完组后还有剩余，则将最后 \(1\) 个数放入第 \(3\) 组中。
这样我们就有效的将 \(1\) 组数分成了 \(3\) 组。
继续观察，由于第 \(3\) 组数可以直接求解，因此不作讨论。
对于第 \(1\), \(2\) 组数，不难发现它们之间存在倍数关系。
具体地，若令 \(S_1\) 表示第 \(1\) 组数之和，\(S_2\) 表示第 \(2\) 组数之和，则有：
那么对于 \(S_1\) 和 \(S_2\) 该如何求解呢？
递归！
// 快速幂代码就不给了
int solve(int a, int n){
// 递归出口
if(n == 1) return 1 % p;
int res = 0;
if(n%2){ // 如果 n 为奇数，则说明存在第 3 组数
res = fpm(a, n-1); // 快速幂求解
}
res = add(res, mul(add(1, fpm(a, n/2)), solve(a, n/2)));
/* 此行原本应写成:
res += (1 + fpm(a, n/2)) * solve(a, n/2);
其中 add 和 mul 分别为手写加法和乘法运算，并自动取模 */
return res;
}