题解 | 斐波那契字符串

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const ll MOD = 1e9 + 7;

const int MAXN = 1e5;
ll zero[MAXN+5], one[MAXN+5], ans[MAXN+5];

void init() {
    zero[1] = 1; one[1] = 0; ans[1] = 0;
    zero[2] = 0; one[2] = 1; ans[2] = 0;
    zero[3] = 1; one[3] = 1; ans[3] = 0;
    for (int i = 4; i <= MAXN; ++i) {
        zero[i] = (zero[i-2] + zero[i-1]) % MOD;
        one[i]  = (one[i-2] + one[i-1]) % MOD;
        ans[i]  = (ans[i-2] + ans[i-1] + one[i-2] * zero[i-1] % MOD) % MOD;
    }
}
void solve() {
    int i{};
    cin>>i;
    cout<<ans[i]<<'\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}