题解 | 斐波那契字符串

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[300005],one[300005],zero[300005];
LL t;
LL n;
void han(){
    for(int i=3;i<=300000;i++){
        a[i]=(one[i-2]*zero[i-1]+a[i-1]+a[i-2])%(long long)(1e9+7);
        one[i]=(one[i-2]+one[i-1])%(long long)(1e9+7);
        zero[i]=(zero[i-2]+zero[i-1])%(long long)(1e9+7);
    }
    return ;
}
int main(){
    cin>>t;
    a[1]=0;
    a[2]=0;
    one[1]=0;
    one[2]=1;
    zero[1]=1;
    zero[2]=0;
    han();

    while(t--){
        cin>>n;
        cout<<a[n]<<'\n';
    }
	return 0;
}