思路与算法

补充 $F_0=0$，使用列向量 $V_i=(F_i,F_{i-1})^\mathsf T$。递推可写作

$$V_{i+1}=Q V_i,\quad Q=\begin{pmatrix}1&1\\1&0\end{pmatrix}.$$

初始向量 $V_1=(1,0)^\mathsf T$，所以 $V_n=Q^{n-1}V_1$。用二进制快速幂计算矩阵幂，结果从单位矩阵开始，指数为1的二进制位将当前矩阵乘入结果，每轮把底矩阵平方、指数右移。最后取向量第一项并模 $m$。本题每次输入同时给 $n,m$，与固定模数版本协议不同。

正确性说明

转移第一行给出 $F_i+F_{i-1}=F_{i+1}$，第二行复制 $F_i$，故一次矩阵乘法正确地把状态推进一项。由初始向量归纳，连续推进 $n-1$ 次得到 $V_n$。快速幂循环保持“结果矩阵乘当前底矩阵的剩余指数次幂”等于目标幂，拆出奇数位并平方不会改变该值；指数归零时结果即目标矩阵。整数模运算保持加乘同余，故输出为所求余数。

复杂度

设状态维度为 $d$（本题为固定常数）。初始化转移矩阵和单位矩阵耗时 $O(d^2)$；一次矩阵乘法 $O(d^3)$，二进制幂进行 $O(\log(n+1))$ 轮，最后矩阵乘初始向量 $O(d^2)$。含初始化总时间 $O(d^2+d^3\log(n+1))$，固定维度可简为 $O(\log(n+1))$。矩阵和向量额外空间 $O(d^2)$，不按 $n$ 分配数组。

易错点

1. 初始位置是1，幂为 $n-1$；$n=1$ 时用零次幂单位矩阵。
2. 模数可以为1，单位矩阵对角元也按 $1\bmod m$ 初始化，结果为0。
3. 使用列向量，矩阵与向量的乘法方向一致。输入的 $m$ 必须参与每次模运算。
4. 全部乘法采用64位，模数至 $10^9+10$，模内乘积及即时约简的累加均安全。
5. 最大 $n$ 不可逐项递推；独立答案用倍增公式，并以800个小范围逐项递推用例交叉验证。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int D = 2;
ll mod;
struct Matrix {
    ll a[D][D]{};
};
Matrix multiply(const Matrix &x, const Matrix &y) {
    Matrix out;
    for (int i = 0; i < D; i++)
        for (int j = 0; j < D; j++)
            for (int k = 0; k < D; k++)
                out.a[i][j] = (out.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
    return out;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n >> mod;
    ll raw[D][D] = {{1, 1}, {1, 0}};
    Matrix base, result;
    for (int i = 0; i < D; i++) {
        result.a[i][i] = 1 % mod;
        for (int j = 0; j < D; j++)
            base.a[i][j] = raw[i][j] % mod;
    }
    ll power = n - 1;
    while (power) {
        if (power & 1)
            result = multiply(result, base);
        base = multiply(base, base);
        power >>= 1;
    }
    ll initial[D] = {1, 0}, answer = 0;
    for (int j = 0; j < D; j++)
        answer = (answer + result.a[0][j] * initial[j]) % mod;
    cout << answer << '\n';
}