题解 | 超级斐波那契数列

先设立一个 量级的答案数组，便于查询。将 位置的答案设置为 ，之后的位置的答案就用滑动窗口处理。窗口的长度始终保持在 长度，由于我一开始就先建立好了窗口，所以每次先更新答案，后更新窗口。最后查询答案就好。

时间复杂度为。

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

const int MAXN = 1e6 + 5;
const int mod = 1e9 + 7;
int main() {
    int k, q;
    cin >> k >> q;
    vector<long long> s(MAXN);
    for(int i = 1;i <= k;i++)   s[i] = 1;
    long long sum = k;
    for(int i = k + 1;i < MAXN;i++){
        s[i] = sum;
        sum = (sum + s[i]) % mod;
        sum = (sum - s[i - k] + mod) % mod;
    }
    while(q--){
        int x;
        cin >> x;
        cout << s[x] << "\n";
    }
    return 0;
}