菲波那契数列(2)

题目描述

菲波那契数列： $f(1) = f(2) = 1$ ， $f(i) = f(i-1) + f(i-2)$ （ $i \geqslant 3$ ）。

第一行是组数 $n$ ，后面 $n$ 行每行一个正整数 $a$ （ $1 \leqslant a \leqslant 10^6$ ），对每个 $a$ 输出 $f(a) \bmod 1000$ 。

样例输入（每组一行）：4 5 2 19 1，样例输出：5 1 181 1。

思路

多组询问共享同一个数列：先一次线性递推到 $\max a$ ，把每个 $f(i) \bmod 1000$ 存进全局数组，之后每问 $O(1)$ 查表。同余对加法封闭，边算边取模不影响结果。总复杂度 $O(\max a + n)$ 。

参考代码

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#!/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-29 22:38
# update_at: 2026-09-29 22:38

import sys

MOD = 1000  # 题目要求的模数


def fib_table(limit: int) -> list[int]:
    """fib[i] = 第 i 个斐波那契数对 1000 取模，下标从 1 开始，只算到 limit。"""
    fib = [0, 1, 1]  # f(1) = f(2) = 1，占住下标 0/1/2
    for i in range(3, limit + 1):
        fib.append((fib[i - 1] + fib[i - 2]) % MOD)  # 每步取模，数值不溢出、表恒为三位数以内
    return fib


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)  # 测试组数
    queries = [next(data) for _ in range(T)]  # 先收齐全部询问，才知道要预计算到哪个位置

    fib = fib_table(max(queries))  # 一次线性递推，所有询问共享同一张表
    print('\n'.join(map(str, (fib[a] for a in queries))))


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/**
 * 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-05 04:48
 * update_at: 2026-10-05 04:48
 */

#include <cstdio>

typedef long long ll;

const int MAXA = 1000000 + 5;
const int MOD = 1000;

// fib[i] = 菲波那契数列第 i 项对 1000 取模的结果
ll fib[MAXA];

int main() {
    // 预计算：所有询问共享同一张表，先递推到最大的可能下标
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= MAXA - 5; ++i) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % MOD; // 同余对加法封闭，边算边取模
    }

    int n;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 1; i <= n; ++i) {
        int a;
        scanf("%d", &a);
        printf("%lld\n", fib[a]); // 每问 O(1) 查表
    }
    return 0;
}

目录

题目描述

思路

参考代码