1643：【例 3】Fibonacci 前 n 项和

题目描述

大家都知道 Fibonacci 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,\dots ,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

5 1000

样例输出 #1

12

样例解释 #1

Fibonacci 数列前 $5$ 项：$1,1,2,3,5$，和 $S_5 = 1+1+2+3+5 = 12$。

$12 \bmod 1000 = 12$。

数据范围

对于 $100\%$ 的数据：

• $1 \le n \le 2 \times 10^9$
• $1 \le m \le 10^9 + 10$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：$n$ 很大，不能直接求和。需要利用矩阵快速幂加速。

我们知道 Fibonacci 数列的递推关系：$f_n = f_{n-1} + f_{n-2}$。前 $n$ 项和 $S_n = f_1 + f_2 + \dots + f_n$。也有递推关系：$S_n = S_{n-1} + f_n$，但这样仍然需要递推。

更好的方法是将 $S_n$ 也纳入状态向量。考虑状态向量：

$$\mathbf{F}_n = \begin{bmatrix} f_{n+1} \\ f_n \\ S_n \end{bmatrix}$$

我们希望找到转移矩阵 $A$，使得 $\mathbf{F}_n = A \cdot \mathbf{F}_{n-1}$。

已知：

• $f_{n+1} = f_n + f_{n-1}$
• $f_n = f_n$
• $S_n = S_{n-1} + f_n$

但 $\mathbf{F}_{n-1} = \begin{bmatrix} f_n \\ f_{n-1} \\ S_{n-1} \end{bmatrix}$，我们需要用 $f_n, f_{n-1}, S_{n-1}$ 表示 $f_{n+1}, f_n, S_n$：

• $f_{n+1} = 1 \cdot f_n + 1 \cdot f_{n-1} + 0 \cdot S_{n-1}$
• $f_n = 1 \cdot f_n + 0 \cdot f_{n-1} + 0 \cdot S_{n-1}$
• $S_n = 1 \cdot f_n + 0 \cdot f_{n-1} + 1 \cdot S_{n-1}$

所以转移矩阵为：

$$A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}$$

验证：$\mathbf{F}_n = A \cdot \mathbf{F}_{n-1}$。

初始状态 $\mathbf{F}_1 = \begin{bmatrix} f_2 \\ f_1 \\ S_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$。

那么 $\mathbf{F}_n = A^{n-1} \cdot \mathbf{F}_1$。我们需要的是 $S_n$，即 $\mathbf{F}_n$ 的第三个分量。

因此，算法步骤：

1. 构造 $3 \times 3$ 矩阵 $A$ 和初始向量 $F_1$。
2. 计算 $A^{n-1}$（用矩阵快速幂）。
3. 计算 $\mathbf{F}_n = A^{n-1} \cdot F_1$。
4. 输出 $\mathbf{F}_n$ 的第三个元素（即 $S_n$）模 $m$。

注意：当 $n=1$ 时，$n-1=0$，$A^0$ 是单位矩阵，$\mathbf{F}_1 = [1,1,1]^T$，$S_1=1$，正确。

另外，可以直接使用 $2 \times 2$ 矩阵包含和的信息，但 $3 \times 3$ 更清晰。

矩阵快速幂复杂度 $O(3^3 \log n) = O(27 \log n)$，可以接受。

注意取模运算。