题解 | 斐波那契字符串

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t,x,max=2;
    auto *count=new vector<pair<int,int>>(100000);
    auto *pair=new vector<int>(100000); 
    (*count)[1]={1,0};
    (*count)[2]={0,1};
    (*pair)[1]=0;
    (*pair)[2]=0;
    cin>>t;
    while(t--){
        cin>>x;
        if(x<max){
            cout<<(*pair)[x]<<'\n';
            continue;
        }
        for(int i=max+1;i<=x;i++){
            (*pair)[i]=((long long)(*count)[i-1].first*(long long)(*count)[i-2].second+(long long)(*pair)[i-1]+(long long)(*pair)[i-2])%(long long)(1e9+7);
            (*count)[i].first=((*count)[i-1].first+(*count)[i-2].first)%(int)(1e9+7);
            (*count)[i].second=((*count)[i-1].second+(*count)[i-2].second)%(int)(1e9+7);
        }
        max=x;
        cout<<(*pair)[x]<<'\n';
    }
}
// 64 位输出请用 printf("%lld")