题解 | 斐波那契字符串
斐波那契字符串
https://www.nowcoder.com/practice/704ed5d1c4a34227a85e07ff80025351
#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")