练67.1  斐波那契数列

解题思路

预处理F[1]=F[2]=1，后续每次用(F[i-1]+F[i-2])%1000，查询直接取对应位置。先读全部查询，以最大a作为预处理上界。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

结果可能为0，不因输出说明写正整数而改动余数。

复杂度

时间O(max a+n)，空间O(max a+n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> q(n);
    int mx = 2;
    for (int &x : q) {
        cin >> x;
        mx = max(mx, x);
    }
    vector<int> f(mx + 1);
    f[1] = f[2] = 1;
    for (int i = 3; i <= mx; i++)
        f[i] = (f[i - 1] + f[i - 2]) % 1000;
    for (int x : q)
        cout << f[x] << "\n";
    return 0;
}