「一本通 6.5 例 3」Fibonacci 前 n 项和

题目描述

定义 Fibonacci 数列 $f_1 = f_2 = 1$ ， $f_k = f_{k-1} + f_{k-2}$ 。给定 $n, m$ ，求前 $n$ 项和 $S_n = f_1 + f_2 + \cdots + f_n \pmod m$ 。

输入格式：一行两个整数 $n\ m$ 。输出格式：一行一个整数表示 $S_n \bmod m$ 。

样例：输入 5 1000，输出 12。数据范围： $1 \le n \le 2 \times 10^9$ ， $1 \le m \le 10^9 + 10$ 。

思路

前缀和满足恒等式 $S_n = f_{n+2} - 1$ ，于是只需求第 $n+2$ 项。Fibonacci 是二阶线性递推，用 $2 \times 2$ 转移矩阵 $T = \begin{pmatrix}1&1\\1&0\end{pmatrix}$ 的快速幂可在 $O(\log n)$ 次乘法内得到 $f_{n+2}$ ，再减 1 取模即为答案。注意 C++ 中负数取模需修正。

参考代码

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#!/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

# 转移矩阵 T：[f(k+1), f(k)] · T = [f(k+2), f(k+1)]，且 T^k 的左上角就是 f(k+1)
FIB = ((1, 1), (1, 0))


def mat_mul(a: tuple, b: tuple, m: int) -> tuple:
    """2×2 矩阵乘法，边乘边对 m 取模。"""
    return tuple(
        tuple(sum(a[i][k] * b[k][j] for k in range(2)) % m for j in range(2))
        for i in range(2)
    )


def mat_pow(base: tuple, n: int, m: int) -> tuple:
    """矩阵快速幂：返回 base^n mod m，O(log n) 次矩阵乘法。"""
    result = ((1, 0), (0, 1))  # 单位矩阵
    while n:
        if n & 1:
            result = mat_mul(result, base, m)
        base = mat_mul(base, base, m)
        n >>= 1
    return result


def solve() -> None:
    n, m = map(int, sys.stdin.buffer.read().split())

    # 恒等式 S_n = f_1 + ... + f_n = f_{n+2} - 1，
    # 而 T^(n+1) 的左上角是 f_{n+2}，故只需一次矩阵快速幂。
    print((mat_pow(FIB, n + 1, m)[0][0] - 1) % m)


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
63
64
65
66
67
68
69
70/**
 * 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 01:29
 * update_at: 2026-10-06 01:29
 */

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

ll n, m;

// 2×2 矩阵乘法，边乘边对 m 取模
void mat_mul(ll a[2][2], ll b[2][2], ll res[2][2]) {
    ll tmp[2][2];
    tmp[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % m;
    tmp[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % m;
    tmp[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % m;
    tmp[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % m;
    res[0][0] = tmp[0][0];
    res[0][1] = tmp[0][1];
    res[1][0] = tmp[1][0];
    res[1][1] = tmp[1][1];
}

// 矩阵快速幂：返回 base^p mod m
void mat_pow(ll base[2][2], ll p, ll ans[2][2]) {
    // ans 初始化为单位矩阵
    ans[0][0] = 1; ans[0][1] = 0;
    ans[1][0] = 0; ans[1][1] = 1;
    ll cur[2][2];
    cur[0][0] = base[0][0]; cur[0][1] = base[0][1];
    cur[1][0] = base[1][0]; cur[1][1] = base[1][1];
    while (p) {
        if (p & 1) {
            ll t[2][2];
            mat_mul(ans, cur, t);
            ans[0][0] = t[0][0]; ans[0][1] = t[0][1];
            ans[1][0] = t[1][0]; ans[1][1] = t[1][1];
        }
        ll t[2][2];
        mat_mul(cur, cur, t);
        cur[0][0] = t[0][0]; cur[0][1] = t[0][1];
        cur[1][0] = t[1][0]; cur[1][1] = t[1][1];
        p >>= 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    if (m == 1) {
        cout << 0 << "\n";
        return 0;
    }
    // 转移矩阵 T = [[1,1],[1,0]]
    ll T[2][2] = {{1, 1}, {1, 0}};
    // 恒等式 S_n = f_{n+2} - 1，T^(n+1) 的左上角即为 f_{n+2}
    ll P[2][2];
    mat_pow(T, n + 1, P);
    ll ans = (P[0][0] - 1) % m;
    if (ans < 0) ans += m;
    cout << ans << "\n";
    return 0;
}

「一本通 6.5 例 3」Fibonacci 前 n 项和

目录

题目描述

思路

参考代码