斐波那契前 n 项和
大家都知道 Fibonacci 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3, \ldots ,f_n=f_{n−1}+f_{n−2}$。
现在问题很简单，输入 $n$ 和 $m$，求 $f_n$ 的前 $n$ 项和 $S_n \bmod m$。
输入格式
共一行，包含两个整数 $n$ 和 $m$。
输出格式
输出前 $n$ 项和 $S_n \bmod m$ 的值。
数据范围
$1 \leq n \leq 2000000000$,
$1 \leq m \leq 1000000010$
输入样例：
5 1000
输出样例：
12
解题思路
遇到递推的题目想想能不能构造出矩阵，然后通过矩阵乘法和快速幂来快速求出第$n$项是什么。
设斐波那契的第$n$项为$f_n$，定义向量$F_n = \begin{bmatrix} f_n & f_{n+1} \end{bmatrix}$，那么$F_{n+1} = \begin{bmatrix} f_{n+1} & f_{n+2} \end{bmatrix}$。尝试构造一个$2 \times 2$的矩阵$A$使得$F_n \times A = F_{n+1}$。容易发现$$\begin{bmatrix} f_n & f_{n+1} \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} f_{n+1} & f_{n+2} \end{bmatrix}$$
因此$A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$。同时根据矩阵乘法的结合律，有$F_n = F_1 \times A^{n-1}$，$A^{n-1}$可以用快速幂来算。
现在的问题是求斐波那契的前$n$项和$S_n = \sum\limits_{i=1}^{n}{f_n}$。那么我们构造向量$F_n = \begin{bmatrix} f_n & f_{n+1} & S_n \end{bmatrix}$，继续找到一个$3 \times 3$的矩阵$A$使得$F_n \times A = F_{n+1}$。同样有$$\begin{bmatrix} f_n & f_{n+1} & S_n \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} f_{n+1} & f_{n+2} & S_{n+1} \end{bmatrix}$$
那么$A = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$。$F_n = F_1 \times A^{n-1}$，其中$F_1 = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$。
AC代码如下，时间复杂度为$O\left( 3^3 \times \log{n} \right)$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int n, m;
5 int a[3][3] = {
6 {0, 1, 0},
7 {1, 1, 1},
8 {0, 0, 1}
9 };
10
11 void mul(int c[], int a[], int b[][3]) { // c = a * b
12 int tmp[3] = {0};
13 for (int i = 0; i < 3; i++) {
14 for (int j = 0; j < 3; j++) {
15 tmp[i] = (tmp[i] + 1ll * a[j] * b[j][i]) % m;
16 }
17 }
18 memcpy(c, tmp, sizeof(tmp));
19 }
20
21 void mul(int c[][3], int a[][3], int b[][3]) { // c = a * b
22 int tmp[3][3] = {0};
23 for (int i = 0; i < 3; i++) {
24 for (int j = 0; j < 3; j++) {
25 for (int k = 0; k < 3; k++) {
26 tmp[i][j] = (tmp[i][j] + 1ll * a[i][k] * b[k][j]) % m;
27 }
28 }
29 }
30 memcpy(c, tmp, sizeof(tmp));
31 }
32
33 int main() {
34 cin >> n >> m;
35 int f1[3] = {1, 1, 1};
36 n--;
37 while (n) {
38 if (n & 1) mul(f1, f1, a); // f1 = f1 * a
39 mul(a, a, a); // a = a * a
40 n >>= 1;
41 }
42 cout << f1[2];
43
44 return 0;
45 }
为了方便统一成两个矩阵的乘法，可以把$F_1$扩展为$3 \times 3$的矩阵$F1 = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int n, m;
5 int a[3][3] = {
6 {0, 1, 0},
7 {1, 1, 1},
8 {0, 0, 1}
9 };
10
11 void mul(int c[][3], int a[][3], int b[][3]) {
12 int tmp[3][3] = {0};
13 for (int i = 0; i < 3; i++) {
14 for (int j = 0; j < 3; j++) {
15 for (int k = 0; k < 3; k++) {
16 tmp[i][j] = (tmp[i][j] + 1ll * a[i][k] * b[k][j]) % m;
17 }
18 }
19 }
20 memcpy(c, tmp, sizeof(tmp));
21 }
22
23 int main() {
24 cin >> n >> m;
25 int f1[3][3] = {1, 1, 1};
26 n--;
27 while (n) {
28 if (n & 1) mul(f1, f1, a);
29 mul(a, a, a);
30 n >>= 1;
31 }
32 cout << f1[0][2];
33
34 return 0;
35 }
参考资料
AcWing 1303. 斐波那契前 n 项和（算法提高课）：https://www.acwing.com/video/704/
标签：tmp,begin,end,int,times,斐波,bmatrix,契前 From： https://www.cnblogs.com/onlyblues/p/17070871.html