题解 | 斐波那契字符串

#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9+7;
const int maxn = 100001;
vector<long long > dp(maxn, 0); //全局变量dp，存储每个sn的逆序对总数
void precompute(){ // 预处理函数，牺牲空间，使得T--循环，每次求Sn时的查询时间复杂度降维至O(n)
    vector<long long> zeros(maxn,0);
    vector<long long> ones(maxn,0);
    zeros[1] = 1;
    ones[2]  = 1;
    for (int i = 3; i < maxn; i++) {
        zeros[i] = (zeros[i-1] + zeros[i-2]) % mod;
        ones[i] = (ones[i-1] + ones[i-2]) % mod; // zero和one同样遵守斐波那契递推
        long long cross_inversions = (ones[i - 2] * zeros[i - 1]) % mod;
        // cross_inversions中ones数组的下标要在zeros下标的前面，因为Sn的逆序对的计算还有一部分
        // 是Sn-2的“1”与Sn-1的"0"组合而成
        dp[i] = (dp[i - 2] + dp[i - 1] + cross_inversions) % mod;
    }
}

void solve(){ // 查询函数，时间复杂度O(n)
    int n;
    cin >> n;
    cout << dp[n] << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}