题解 | 斐波那契字符串

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;

struct fibostr {
    long long one;     // 实际存储 one % MOD
    long long zero;    // 实际存储 zero % MOD
    long long reverses;
    
    fibostr(long long o, long long z, long long r) 
        : one(o % MOD), zero(z % MOD), reverses(r % MOD) {}
};

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

    vector<fibostr> arr;
    arr.reserve(100001);
    // S3: "01" → one=1, zero=1, rev=0
    // S4: "101" → one=2, zero=1, rev=1
    arr.emplace_back(1, 1, 0);
    arr.emplace_back(2, 1, 1);

    int T;
    cin >> T;
    while (T--) {
        int k;
        cin >> k;

        // 扩展到至少 k-2 个元素（arr[0] = S3, ..., arr[k-3] = Sk）
        while ((int)arr.size() < k - 2) {
            int i = arr.size();
            long long new_one = (arr[i-2].one + arr[i-1].one) % MOD;
            long long new_zero = (arr[i-2].zero + arr[i-1].zero) % MOD;
            long long cross = (arr[i-2].one * arr[i-1].zero) % MOD;
            long long new_rev = (arr[i-2].reverses + arr[i-1].reverses + cross) % MOD;
            arr.emplace_back(new_one, new_zero, new_rev);
        }

        long long res = arr[k-3].reverses % MOD;
        if (res < 0) res += MOD; // 防御性编程（其实不会负，但保险）
        cout << res << '\n';
    }
    return 0;
}