「一本通 6.5 练习 1」Fibonacci

形式化题目

给定若干个独立的查询，每个查询包含一个非负整数 $n$ 。已知斐波那契数列的递推关系为：

F_0 = 0, \quad F_1 = 1, \quad F_k = F_{k-1} + F_{k-2} \quad (k \ge 2)

对每个查询，计算并输出

F_n \bmod 10^4

的值。

正解

思路

对于 $n \le 10^9$ 的数据范围，朴素按定义循环递推 $F_k = (F_{k-1} + F_{k-2}) \bmod 10^4$ 的时间复杂度为 $O(n)$ ，在 $n$ 较大时会严重超时。

观察斐波那契数列的线性递推关系：

\begin{cases} F_{k+1} = 1 \cdot F_k + 1 \cdot F_{k-1} \\ F_k = 1 \cdot F_k + 0 \cdot F_{k-1} \end{cases}

将状态向量表示为列向量 $\begin{pmatrix} F_{k+1} \\ F_k \end{pmatrix}$ ，上述递推可以用 $2 \times 2$ 的转移矩阵表示：

\begin{pmatrix} F_{k+1} \\ F_k \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_k \\ F_{k-1} \end{pmatrix}

连续应用该矩阵变换，得到：

\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}

更进一步，利用数学归纳法可知：

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}

因此，记转移矩阵 $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ ，只要利用矩阵快速幂求出 $A^n \pmod{10^4}$ ，其第 0 行第 1 列（0-indexed）的元素恰好就是 $F_n \bmod 10^4$ 。

当 $n = 0$ 时，直接输出 $0$ （或者依据 $A^0 = I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ ，右上角元素同样为 $0$ ）。

代码

Python 版：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#!/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-03-31 09:00
# update_at: 2026-03-31 09:00

import sys

MOD = 10000  # 题目要求的模数
Matrix2x2 = tuple[int, int, int, int]  # 行优先展平表示 2x2 矩阵 (m00, m01, m10, m11)
TRANS: Matrix2x2 = (1, 1, 1, 0)        # 斐波那契状态转移矩阵 [[1, 1], [1, 0]]
I2: Matrix2x2 = (1, 0, 0, 1)           # 2x2 单位矩阵


def mat_mul(a: Matrix2x2, b: Matrix2x2) -> Matrix2x2:
    """计算两个 2x2 矩阵的乘积模 10000。"""
    return (
        (a[0] * b[0] + a[1] * b[2]) % MOD,
        (a[0] * b[1] + a[1] * b[3]) % MOD,
        (a[2] * b[0] + a[3] * b[2]) % MOD,
        (a[2] * b[1] + a[3] * b[3]) % MOD,
    )


def mat_pow(base: Matrix2x2, exp: int) -> Matrix2x2:
    """计算 2x2 矩阵的 exp 次幂模 10000。"""
    res = I2
    while exp:
        if exp & 1:
            res = mat_mul(res, base)
        base = mat_mul(base, base)
        exp >>= 1
    return res


def fib(n: int) -> int:
    """计算第 n 项斐波那契数模 10000。"""
    if n == 0:
        return 0
    # [[F_{n+1}, F_n], [F_n, F_{n-1}]] = [[1, 1], [1, 0]]^n
    # 所以 TRANS^n 的右上方元素（下标 1）即为 F_n
    return mat_pow(TRANS, n)[1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    for n in data:
        if n == -1:
            break
        out.append(str(fib(n)))
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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:18
 * update_at: 2026-10-06 00:18
 */

#include <cstdio>

typedef long long ll;

const ll MOD = 10000; // 题目要求对 10^4 取模

// 2x2 矩阵乘法：c = a * b (mod MOD)，c 必须与 a、b 是不同的数组
void mat_mul(ll a[2][2], ll b[2][2], ll c[2][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
}

// 计算斐波那契数列第 n 项模 MOD，用转移矩阵的快速幂，复杂度 O(log n)
ll fib(ll n) {
    ll res[2][2] = {{1, 0}, {0, 1}};   // 单位矩阵，快速幂累积结果
    ll base[2][2] = {{1, 1}, {1, 0}};  // 斐波那契转移矩阵 A
    ll tmp[2][2];                       // 矩阵乘法的临时结果
    while (n > 0) {
        if (n & 1) {
            mat_mul(res, base, tmp);
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    res[i][j] = tmp[i][j];
                }
            }
        }
        mat_mul(base, base, tmp);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                base[i][j] = tmp[i][j];
            }
        }
        n >>= 1;
    }
    // A^n = [[F_{n+1}, F_n], [F_n, F_{n-1}]]，右上角元素恰好是 F_n
    return res[0][1];
}

int main() {
    ll n;
    while (scanf("%lld", &n) == 1) {
        if (n == -1) {
            break;
        }
        printf("%lld\n", fib(n));
    }
    return 0;
}

复杂度

时间复杂度：设询问组数为 $T$ 。对于每个询问 $n$ ，二进制位数为 $\lfloor \log_2 n \rfloor + 1$ 。每次 $2 \times 2$ 矩阵乘法仅包含 $8$ 次乘法和 $4$ 次加法取模，耗时为常数 $O(1)$ 。因此单次计算复杂度为 $O(\log n)$ ，整体时间复杂度为 $O(T \log n)$ 。
空间复杂度：仅需常数级别的变量存储 $2 \times 2$ 矩阵，空间复杂度为 $O(1)$ 。

总结

线性递推式的核心优化手段是构建状态转移矩阵，将单步 $O(1)$ 的状态推进提升为矩阵乘法，进而利用矩阵快速幂将 $O(n)$ 的线性递推压制到 $O(\log n)$ 。

在实现时，2 阶方阵状态较小，使用展平的元组或简单的常数循环即可高效完成乘法，每步对 $10^4$ 取模保证数值不溢出。

图示解析

状态向量与转移矩阵关系如下：

flowchart LR
    subgraph S0["基础向量 (k=0)"]
        V0["[F1, F0]^T = [1, 0]^T"]
    end
    subgraph Mul["矩阵连续作用"]
        A["乘以矩阵 A = [[1, 1], [1, 0]]"]
    end
    subgraph Sn["目标状态 (第 n 步)"]
        Vn["[F(n+1), Fn]^T = A^n * [1, 0]^T"]
    end

    V0 -->|快速幂倍增 log n 次| Mul --> Vn

矩阵乘法规则（对模 $10^4$ 取模）：

\begin{pmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{pmatrix} \times \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{pmatrix} = \begin{pmatrix} (a_{00}b_{00} + a_{01}b_{10})\bmod M & (a_{00}b_{01} + a_{01}b_{11})\bmod M \\ (a_{10}b_{00} + a_{11}b_{10})\bmod M & (a_{10}b_{01} + a_{11}b_{11})\bmod M \end{pmatrix}