题解 | 斐波那契字符串

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

const int MAXN = 100000 + 5;
const long long MOD = 1000000007;

long long oneCnt[MAXN], zeroCnt[MAXN], invCnt[MAXN];

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

    int T; cin >> T;
    vector<int> queries(T);
    int maxn = 0;
    for (int i = 0; i < T; i++) {
        cin >> queries[i];
        maxn = max(maxn, queries[i]);
    }

    // 初始化
    oneCnt[1] = 0; zeroCnt[1] = 1; invCnt[1] = 0;
    oneCnt[2] = 1; zeroCnt[2] = 0; invCnt[2] = 0;

    for (int i = 3; i <= maxn; i++) {
        oneCnt[i] = (oneCnt[i-2] + oneCnt[i-1]) % MOD;
        zeroCnt[i] = (zeroCnt[i-2] + zeroCnt[i-1]) % MOD;

        // 使用 % 避免溢出
        long long cross = (oneCnt[i-2] * zeroCnt[i-1]) % MOD;
        invCnt[i] = (invCnt[i-2] + invCnt[i-1] + cross) % MOD;
    }

    for (int i = 0; i < T; i++) {
        cout << invCnt[queries[i]] << "\n";
    }

    return 0;
}