「一本通 6.5 例 4」佳佳的 Fibonacci

题目描述

佳佳定义 $T(n)=(F_1+2F_2+\cdots+nF_n)\bmod m$ ，其中 $F_1=F_2=1,\ F_i=F_{i-1}+F_{i-2}$ ；给定 $n,m$ 求 $T(n)$ 。输入一行两个整数 $n,m$ （ $1\leqslant n,m\leqslant 2^{31}-1$ ），输出一行 $T(n)$ 。样例输入 5 5，样例输出 1。

思路

由恒等式 $T(n)=nF_{n+2}-F_{n+3}+2$ ，只需算出 $F_{n+2},F_{n+3}$ ；用快速倍增在 $O(\log n)$ 内得到相邻 Fibonacci 对，再代入公式取模。

参考代码

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


def fib_pair(n: int, mod: int) -> tuple[int, int]:
    """返回 (F(n) mod m, F(n+1) mod m)：快速倍增，由 F(k),F(k+1) 一步翻倍到 F(2k),F(2k+1)。"""
    if n == 0:
        return (0, 1 % mod)              # m = 1 时所有 Fibonacci 值都应输出 0
    a, b = fib_pair(n >> 1, mod)         # a = F(k), b = F(k+1)，k = ⌊n/2⌋
    c = a * (2 * b - a) % mod            # F(2k)   = F(k) · (2F(k+1) - F(k))
    d = (a * a + b * b) % mod            # F(2k+1) = F(k)² + F(k+1)²
    if n & 1:                            # n 是奇数：再从 F(2k), F(2k+1) 走一步
        return (d, (c + d) % mod)
    return (c, d)


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

    fn, fn1 = fib_pair(n, m)
    fn2 = (fn + fn1) % m                 # F(n+2)
    fn3 = (fn1 + fn2) % m                # F(n+3)
    # 恒等式 T(n) = Σ i·F(i) = n·F(n+2) - F(n+3) + 2 (mod m)，推导见题解
    print((n * fn2 - fn3 + 2) % 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/**
 * 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:30
 */
#include <cstdio>
#include <utility>
using namespace std;

typedef long long ll;

ll n, m; // n 为求和上界，m 为取模数

// 快速倍增：返回 (F(k) mod m, F(k+1) mod m)，每层用半规模的一对值翻倍得到整规模
pair<ll, ll> fib_pair(ll k) {
    if (k == 0) {
        return make_pair(0LL, 1 % m); // k = 0 时 (F(0), F(1)) = (0, 1)，m = 1 时归零
    }
    pair<ll, ll> half = fib_pair(k >> 1);
    ll a = half.first;  // F(k/2)
    ll b = half.second; // F(k/2 + 1)
    // F(2t) = F(t) * (2F(t+1) - F(t))，先取模再乘，避免 2b - a 为负
    ll c = a * (((2 * b - a) % m + m) % m) % m;
    // F(2t+1) = F(t)^2 + F(t+1)^2，两项分开取模防止相加溢出
    ll d = ((a * a) % m + (b * b) % m) % m;
    if (k & 1) {
        return make_pair(d, (c + d) % m); // 奇数再走一步
    }
    return make_pair(c, d);
}

int main() {
    scanf("%lld %lld", &n, &m);

    pair<ll, ll> p = fib_pair(n);
    ll fn = p.first;    // F(n)
    ll fn1 = p.second;  // F(n+1)
    ll fn2 = (fn + fn1) % m;   // F(n+2)
    ll fn3 = (fn1 + fn2) % m;  // F(n+3)

    // 恒等式 T(n) = sum(i * F(i)) = n * F(n+2) - F(n+3) + 2 (mod m)
    ll ans = ((n % m) * fn2 % m - fn3 + 2) % m;
    ans = (ans + m) % m; // 加法结果可能为负，修正到 [0, m)
    printf("%lld\n", ans);
    return 0;
}

「一本通 6.5 例 4」佳佳的 Fibonacci

目录

题目描述

思路

参考代码