题解 | 斐波那契字符串

#include <iostream>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const int MAX_N=1e5+5;

//对数，1的数量，0的数量
ll cnt0[MAX_N],cnt1[MAX_N],ans[MAX_N];
void solve(){
    ans[1]=0;cnt0[1]=1;cnt1[1]=0;
    ans[2]=0;cnt0[2]=0;cnt1[2]=1;
    for(int i=3;i<MAX_N;i++){
        cnt0[i]=(cnt0[i-1]+cnt0[i-2])%MOD;
        cnt1[i]=(cnt1[i-1]+cnt1[i-2])%MOD;
        ans[i]=(ans[i-1]+ans[i-2]+cnt1[i-2]*cnt0[i-1])%MOD;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<ans[n]<<"\n";
    }
    return 0;
}