题解 | 斐波那契字符串

#include <iostream>
#define int long long
using namespace std;
const int MOD = 1000000007;
signed main() {
    int fbnn[100009];
    int ni[100009];
    fbnn[1]=0;fbnn[2]=1;
    ni[1]=0;ni[2]=1;
    for(int i=3;i<100009;i++){
        fbnn[i]=(fbnn[i-2]+fbnn[i-1])% MOD;
        ni[i]=((fbnn[i]*fbnn[i])% MOD+ni[i-1]+ni[i-2])% MOD;
    }
    int n;cin>>n;
    while(n--){
        int k;cin>>k;
        cout<<ni[k-2]<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")