137 lines
3.0 KiB
Markdown
137 lines
3.0 KiB
Markdown
##[$AcWing$ $1303$. 斐波那契前 $n$ 项和](https://www.acwing.com/problem/content/1305/)
|
||
|
||
### 一、题目描述
|
||
大家都知道 $Fibonacci$ 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n−1}+f_{n−2}$。
|
||
|
||
现在问题很简单，输入 $n$ 和 $m$，求 $f_n$ 的前 $n$ 项和 $S_n \ mod \ m$。
|
||
|
||
**输入格式**
|
||
共一行，包含两个整数 $n$ 和 $m$。
|
||
|
||
**输出格式**
|
||
输出前 $n$ 项和 $S_n\ mod\ m$ 的值。
|
||
|
||
**数据范围**
|
||
$1≤n≤2000000000,1≤m≤1000000010$
|
||
|
||
**输入样例**：
|
||
$5$ $1000$
|
||
|
||
**输出样例**：
|
||
$12$
|
||
|
||
|
||
### 二、解题思路
|
||
普通的迭代法，是线性的，$n$的上限是$2e9$,循环的话会超时，需要想其它办法。
|
||
|
||
**矩阵快速幂**
|
||
|
||
$$\large \begin{bmatrix} s_n & f_{n+1}& f_n \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
a&b &c \\
|
||
d&e & f \\
|
||
h&i & j \\
|
||
\end{bmatrix} = \begin{bmatrix} s_{n+1} & f_{n+2}& f_{n+1} \end{bmatrix}$$
|
||
|
||
$\therefore \\
|
||
s_{n+1}= s_n \times a+f_{n+1} \times d+f_n \times h \\
|
||
f_{n+2}= s_n \times b + f_{n+1} \times e + f_n \times i \\
|
||
f_{n+1}= s_n \times c + f_{n+1} \times f + f_n \times j
|
||
$
|
||
|
||
根据题目的现实含义：
|
||
$s_{n+1}=s_n+f_{n+1}$
|
||
$f_{n+2}=f_n+f_{n+1}$
|
||
|
||
推导出:
|
||
$a=1,d=1,h=0$
|
||
$b=0,e=1,i=1$
|
||
$c=0,f=1,j=0$
|
||
|
||
整理出矩阵就是：
|
||
$m=\begin{bmatrix}
|
||
1 & 0 & 0 \\
|
||
1 & 1 & 1 \\
|
||
0 & 1 & 0
|
||
\end{bmatrix}$
|
||
|
||
已知 $s_1=1，f_2=1，f_1=1$，使用矩阵快速幂可以求解 $s_n$。
|
||
即$b=\begin{bmatrix}
|
||
1 & 1& 1
|
||
\end{bmatrix}$
|
||
|
||
$\begin{bmatrix}s_1 & f_2 & f_1 \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
1 & 0 & 0 \\
|
||
1 & 1 & 1 \\
|
||
0 & 1 & 0
|
||
\end{bmatrix} =\begin{bmatrix}s_2 & f_3 & f_2 \end{bmatrix}
|
||
$ ①
|
||
|
||
$\begin{bmatrix}s_2 & f_3 & f_2 \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
1 & 0 & 0 \\
|
||
1 & 1 & 1 \\
|
||
0 & 1 & 0
|
||
\end{bmatrix} =\begin{bmatrix}s_3 & f_4 & f_3 \end{bmatrix}
|
||
$ ②
|
||
|
||
将 ① 代入 ② 得到：
|
||
|
||
$\begin{bmatrix}s_1 & f_2 & f_1 \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
1 & 0 & 0 \\
|
||
1 & 1 & 1 \\
|
||
0 & 1 & 0
|
||
\end{bmatrix}^2 =\begin{bmatrix}s_3 & f_4 & f_3 \end{bmatrix}
|
||
$
|
||
|
||
通过数学归纳法，得:
|
||
|
||
$\begin{bmatrix}s_1 & f_2 & f_1 \end{bmatrix} \times
|
||
\begin{bmatrix}
|
||
1 & 0 & 0 \\
|
||
1 & 1 & 1 \\
|
||
0 & 1 & 0
|
||
\end{bmatrix}^{n-1} =\begin{bmatrix}s_n & f_{n+1} & f_n \end{bmatrix}
|
||
$
|
||
|
||
|
||
### 三、实现代码
|
||
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
const int N = 3;
|
||
int n, mod;
|
||
|
||
// 矩阵乘法
|
||
void mul(int a[][N], int b[][N], int c[][N]) {
|
||
int t[N][N] = {0};
|
||
for (int i = 0; i < N; i++) {
|
||
for (int j = 0; j < N; j++)
|
||
for (int k = 0; k < N; k++)
|
||
t[i][j] = (t[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
|
||
}
|
||
memcpy(c, t, sizeof t);
|
||
}
|
||
|
||
signed main() {
|
||
int b[N][N] = {1, 1, 1};
|
||
int m[N][N] = {
|
||
{1, 0, 0},
|
||
{1, 1, 1},
|
||
{0, 1, 0}};
|
||
|
||
cin >> n >> mod;
|
||
|
||
for (int i = n - 1; i; i >>= 1) {
|
||
if (i & 1) mul(b, m, b);
|
||
mul(m, m, m);
|
||
}
|
||
printf("%d\n", b[0][0]);
|
||
}
|
||
```
|