形式化题目

Fibonacci 数列由

定义。给定整数 $n, m$（$1 \le n \le 2 \times 10^9$，$1 \le m \le 10^9 + 10$），求

规模瓶颈只有一个：$n$ 大到 $2 \times 10^9$，而 $m$ 只影响乘法是否会溢出（对 Python 不是问题）， 因此全文的优化目标是把「递推 $n-1$ 次」这件事本身加速。

样例 $n = 5, m = 1000$ 的递推过程：

表中最后一列是答案，因此样例输出 5。这张表同时说明了「每一步都可以先取模」： 第三行每一格都是第二行对 1000 取模的结果，继续用它往下推得到的仍然是正确值。

正解

思路

朴素做法及其瓶颈。 最直接的想法是从 $f_1 = f_2 = 1$ 开始往后推 $n-1$ 次，每次加完就取模。 每次迭代 $O(1)$，$n = 5$ 时立刻得到 5，和样例一致；代价是 $O(n)$ 次迭代。 真实数据里 fibo10.in 的 $n = 2 \times 10^9$，20 亿次迭代在 Python 中要几十秒，C++ 也在 1 s 边缘。 问题不在每次迭代做了什么，而在于迭代次数与 $n$ 成正比。

所以关键问题是：能不能找到一种操作，一次就完成「连续推 $k$ 步」，并且这种操作可以合并—— 把 $a$ 步和 $b$ 步合成 $a+b$ 步？能做到，就只需要做 $O(\log n)$ 次操作。

第一步：把「推进一步」写成一个固定的线性变换。 观察递推只用到 $f_k$ 与 $f_{k-1}$ 的线性组合， 把相邻两项看成状态向量：

这一步是可行的，因为递推系数固定：每推进一步都作用同一个矩阵 $M$，与 $k$ 无关。

第二步：把「推 $n-1$ 步」写成矩阵幂。 记 $v_k = (f_{k+1}, f_k)^{\mathsf T}$，则 $v_k = M v_{k-1}$，反复代入得

矩阵乘法满足结合律，这正是「可以合并」的来源：先推 $a$ 步再推 $b$ 步， 等于一次推 $a+b$ 步，因为 $M^a M^b = M^{a+b}$。

具体到答案在哪一格，可以更强地断言：$M^k$ 的左上角就是 $f_{k+1}$。 $k = 0$ 时 $M^0$ 是单位矩阵，左上角 $1 = f_1$；若 $M^k = \begin{pmatrix} f_{k+1} & f_k \\ f_k & f_{k-1}\end{pmatrix}$， 再乘一次 $M$，左上角变成 $f_{k+1} + f_k = f_{k+2}$，归纳成立。取 $k = n-1$ 即得

下表用样例 $n = 5$ 验证这个位置对应关系（取 $m$ 足够大以便观察，不影响结论）：

只关心左上角这一格是本题实现上的关键简化：不需要真的存下整个矩阵用来回溯， 也不需要 $f_0$ 的定义，答案就是 $M^{n-1}$ 的第 0 行第 0 列。

第三步：用倍增快速求幂。 把指数做二进制拆分：若 $e = n-1 = \sum_i 2^{b_i}$， 则 $M^e = \prod_i M^{2^{b_i}}$。于是维护两个矩阵：

• base = $M^{2^{b}}$，$b$ 是当前扫描到的二进制位，每轮平方一次；
• result = 已经累乘进来的那些 $M^{2^{b_i}}$ 的乘积，初始为单位矩阵（$M^0$）。

扫描 $e$ 的每一位：该位为 1 就把 base 乘进 result，然后 base 平方、e 右移一位。 整个过程的正确性由不变量 $n - 1 = (\text{result 的指数}) + 2^{b} \cdot e$ 保证： 每次「乘一次 base」加 $2^b$，「base 平方」把权重翻倍，正好对应 $e$ 右移一位。

指数 $n-1 \le 2 \times 10^9 - 1 < 2^{31}$，最多 31 位，所以只做 $O(\log n)$ 次 2×2 矩阵乘法。 下表是 $n = 10$（即 $e = 9 = 1001_2$）的完整执行过程，也是代码 power() 的逐轮快照：

读法：base 每轮平方，result 只在遇到 1 时更新一次；最后一轮结束后 result 的左上角是 55， 正是 $f_{10}$（$f_{10} = 55$）。注意动作与平方的顺序：先按当前位决定是否乘， 再平方，否则低位的权重会被算成 $2^1$ 而不是 $2^0$。

取模可以随时进行：加法和乘法在 $\mathbb{Z}_m$ 下封闭，即 $(x \bmod m)(y \bmod m) \bmod m = xy \bmod m$，所以每次矩阵乘法后取模不改变最终答案， 而中间值始终不超过 $(m-1)^2 < 10^{18}$。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:43
# update_at: 2026-09-30 23:43

import sys

BASE = ((1, 1), (1, 0))  # 递推矩阵：F(n+1) = F(n) + F(n-1)


def mat_mul(a: tuple, b: tuple, mod: int) -> tuple:
    """2x2 矩阵乘法后取模：结果的第 i 行是 a 的第 i 行分别点乘 b 的两列。"""
    (a00, a01), (a10, a11) = a
    (b00, b01), (b10, b11) = b
    row0 = (a00 * b00 + a01 * b10) % mod, (a00 * b01 + a01 * b11) % mod
    row1 = (a10 * b00 + a11 * b10) % mod, (a10 * b01 + a11 * b11) % mod
    return row0, row1


def power(base: tuple, exp: int, mod: int) -> tuple:
    """矩阵快速幂：base 的 exp 次方，每步取模 m。"""
    result = ((1, 0), (0, 1))  # 单位矩阵，相当于乘法的 1
    while exp:
        if exp & 1:
            result = mat_mul(result, base, mod)
        base = mat_mul(base, base, mod)
        exp >>= 1
    return result


def solve() -> None:
    n, m = map(int, sys.stdin.buffer.read().split())
    # 由 [F(n+1), F(n); F(n), F(n-1)] = BASE^n 得 F(n) 是 BASE^(n-1) 的左上角；
    # n = 1 时幂为 0，单位矩阵的左上角正是 F(1) = 1。
    print(power(BASE, n - 1, m)[0][0] % m)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:12
 * update_at: 2026-10-06 00:12
 */

// main.cpp：Fibonacci 第 n 项 —— 2x2 矩阵快速幂。
// 递推矩阵 M = [[1,1],[1,0]]，f_n 就是 M^(n-1) 的左上角；
// n 可到 2e9，必须用快速幂把 O(n) 递推降到 O(log n)。

#include <cstdio>

typedef long long ll;

ll m; // 模数

// 2x2 矩阵，固定大小直接用全局函数处理
struct Mat {
    ll a[2][2];
};

// 矩阵乘法，结果每个元素都取模
Mat mul(const Mat &x, const Mat &y) {
    Mat z;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) {
            ll sum = 0;
            for (int k = 0; k < 2; ++k)
                sum += x.a[i][k] * y.a[k][j]; // 每项 < m^2 < 2e18，不溢出
            z.a[i][j] = sum % m;
        }
    return z;
}

// 计算 M^e 的左上角：指数二进制拆分，base 每轮平方，该位为 1 时先乘入再平方
ll fib_pow(ll e) {
    Mat base; // base 表示 M^(2^b)，b 是当前扫到的二进制位
    base.a[0][0] = 1; base.a[0][1] = 1;
    base.a[1][0] = 1; base.a[1][1] = 0;

    Mat result; // result 累乘已经扫过的 M^(2^b_i)，初始为单位矩阵 M^0
    result.a[0][0] = 1; result.a[0][1] = 0;
    result.a[1][0] = 0; result.a[1][1] = 1;

    while (e > 0) {
        if (e & 1) result = mul(result, base);
        base = mul(base, base);
        e >>= 1;
    }
    return result.a[0][0]; // M^e 的左上角就是 f_(e+1)
}

int main() {
    ll n; // 要求的项数
    scanf("%lld %lld", &n, &m);

    // 指数为 0（n=1）时 result 是单位矩阵，左上角 1 = f_1，无需特判
    printf("%lld\n", fib_pow(n - 1));
    return 0;
}

复杂度

• 时间复杂度：$O(\log n)$。指数 $n-1$ 有 $\lceil \log_2 n \rceil \le 31$ 位， 每位至多一次乘法加一次平方，单次 2×2 矩阵乘法是常数次运算。
• 空间复杂度：$O(1)$，只保存常数个 2×2 矩阵。

总结

Fibonacci 的递推是常系数线性递推，因此总可以写成固定矩阵的幂； 有了幂，就能用结合律对指数做二进制拆分，把线性的迭代次数压到对数级。 本题的实现要点只有三个：

1. 状态取相邻两项，$M = \begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}$；
2. 答案是 $M^{n-1}$ 的左上角，不需要额外的向量乘法，也不需要特判 $n = 1$（指数 0 时单位矩阵给出 1）；
3. 快速幂中「判断是否乘入」必须发生在平方之前。

同一套推导适用于任何常系数线性递推（如 Pell 数列 $a_n = 2a_{n-1} + a_{n-2}$）， 只要把 $M$ 换成对应的系数矩阵即可。

图示解析

下面这张图只保留从输入到答案的主线，说明每个环节解决了什么问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16输入 n, m（n 可到 2e9）
   │
   ▼
瓶颈：逐项递推要 n-1 次，次数与 n 同阶
   │
   ▼
第一步  状态取相邻两项 → 每步作用同一矩阵 M = [[1,1],[1,0]]
   │     v_k = M · v_(k-1)
   ▼
第二步  合并 n-1 步 → 只需算 M^(n-1)
   │     结合律 M^a · M^b = M^(a+b)
   ▼
第三步  指数二进制拆分 n-1 = Σ 2^b
   │     base 每轮平方；result 遇 1 就乘入
   ▼
答案 = (M^(n-1))[0][0] mod m        时间 O(log n)，空间 O(1)

图中前两层是「为什么慢」，后两层是「怎么变快」：矩阵把递推变成幂，倍增把幂变成 $O(\log n)$ 次乘法。 读者若只想记一句话，可以记成：答案就是递推矩阵的 $n-1$ 次幂的左上角。