1642：【例 2】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 \bmod m$。

输入格式

输入 $n, m$。

输出格式

输出 $f_n \bmod m$。

样例

样例输入 #1

5 1000

样例输出 #1

5

样例解释 #1

Fibonacci 数列：$f_1=1, f_2=1, f_3=2, f_4=3, f_5=5$。

$f_5 \bmod 1000 = 5 \bmod 1000 = 5$。

数据范围

对于 $100\%$ 的数据：

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

时空限制

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

注意：$n$ 很大，不能直接用递推计算。需要使用矩阵快速幂来加速 Fibonacci 数列的计算。

Fibonacci 数列的递推关系可以用矩阵表示为：

$$\begin{bmatrix} f_{n} & f_{n-1} \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2} \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

或者更常见的形式：

$$\begin{bmatrix} f_{n+1} & f_{n} \\ f_{n} & f_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$$

我们通常使用以下方式：设 $F(n) = \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix}$，则 $F(n) = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$。但我们只需要 $f_n$。

更简单的：令 $M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$，则 $M^n = \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix}$。所以要求 $f_n$，只需要计算 $M^n$，然后取右上角（或左下角）的元素。

因此，算法步骤：

1. 定义 $2 \times 2$ 矩阵，并实现矩阵乘法（取模 $m$）。
2. 用快速幂计算 $M^n$。
3. 输出结果矩阵的右上角元素（即 $f_n$）。

注意初始值：$f_1 = 1, f_2 = 1$。对于 $n=1$ 或 $n=2$，可以直接输出 $1 \bmod m$。但矩阵快速幂也可以处理：当 $n=1$ 时，$M^1 = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$，右上角为 $1$，即 $f_1$；当 $n=2$ 时，$M^2 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}$，右上角为 $1$，即 $f_2$。所以对于 $n \ge 1$，计算 $M^{n-1}$ 的右上角？实际上，$M^{n-1}$ 的右上角是 $f_{n-1}$？需要验证。

更常见的方法是：我们想求 $f_n$，可以计算 $M^{n-1}$，然后取左上角？实际上，有公式：

$$\begin{bmatrix} f_n & f_{n-1} \\ f_{n-1} & f_{n-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}$$

所以 $f_n$ 是 $M^{n-1}$ 的左上角元素。验证：$n=1$，$M^0$ 是单位矩阵，左上角为 $1$，即 $f_1$；$n=2$，$M^1$ 左上角为 $1$，即 $f_2$。正确。

因此，计算 $M^{n-1}$，然后输出其左上角元素即可。注意 $n=1$ 时，$n-1=0$，$M^0$ 是单位矩阵，左上角为 $1$。

所以算法：

• 如果 $n \le 2$，直接输出 $1 \bmod m$（但矩阵快速幂已经可以处理）。
• 否则，计算 $M^{n-1}$，取结果矩阵的左上角元素。

注意矩阵乘法取模。由于 $m$ 可能很大（$10^9+10$），但矩阵元素在计算过程中不会超过 $m^2$？实际上，两个元素相乘可能达到 $(10^9)^2 = 10^{18}$，在 long long 范围内。但累加时可能超过 long long？因为最多加两次（$2 \times 2$ 矩阵乘法），所以最大值为 $2 \times (10^9)^2 = 2 \times 10^{18}$，仍然在 long long 范围内（$9.22 \times 10^{18}$）。所以可以用 long long 存储中间结果。

实现矩阵快速幂时，注意单位矩阵是 $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$。