Editorial for Nhịp cầu thời gian

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Từ giá trị trước suy ra giá trị sau

Dãy đã được định nghĩa bằng hai giá trị đầu và công thức cho số hạng tiếp theo. Vì chỉ số lớn nhất là 200000, ta có thể tính lần lượt từ nhỏ đến lớn.

Gợi ý 2 - Đọc truy vấn rồi tiền xử lý một lần

Đọc toàn bộ các chỉ số x và tìm chỉ số lớn nhất. Tính Fibonacci đến chỉ số đó; sau đó mỗi truy vấn chỉ cần in giá trị đã lưu.

Lời giải đầy đủ

Ý tưởng

Tạo mảng fib. Gán fib[0] = 0, fib[1] = 1; với mỗi i >= 2, tính fib[i] = (fib[i-1] + fib[i-2]) mod 1000000007.

Ta lưu truy vấn trước để biết cần tiền xử lý đến đâu. Sau đó in fib[x] cho từng truy vấn theo thứ tự ban đầu.

Độ phức tạp

Gọi X là chỉ số truy vấn lớn nhất. Thời gian O(X+Q), bộ nhớ O(X+Q).

Code C++17

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

const long long MOD = 1'000'000'007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    vector<int> queries(q);
    int maxIndex = 0;
    for (int& x : queries) {
        cin >> x;
        maxIndex = max(maxIndex, x);
    }

    vector<long long> fib(maxIndex + 1, 0);
    if (maxIndex >= 1) fib[1] = 1;
    for (int i = 2; i <= maxIndex; ++i) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    }

    for (int x : queries) cout << fib[x] << endl;
    return 0;
}