题解 | 斐波那契字符串

//考点:斐波那契数列/动态规划dp
#include <iostream>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;
const int MAX = 100005;
ll N[100005];
ll one[100005];
ll zero[100005];//这个斐波那契数列1由前面的1与后面的0决定，单独储存，1与0都各自形成斐波那契
int main() {
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll n, T;
    cin >> T;
    one[1] = 0;one[2] = 1;zero[1] = 1;zero[2] = 0;N[1] = 0;N[2] = 0;N[3] = 0;N[4] = 1, N[5] = 2;
	//初始化
	//以下为拼接过程
	//0  1  01  101  01101  10101101  0110110101101
	//0  0   0  1     2        7
	//one[i-2]*zero[i-1]+N[i-1]+N[i-2]

	//动态规划
    for (int i = 3; i < 100005; i++) {
        one[i] = (one[i - 1] % MOD) + (one[i - 2] % MOD);
        zero[i] = (zero[i - 1] % MOD) + (zero[i - 2] % MOD);
	  
        N[i] = (N[i - 1] % MOD) + (N[i - 2] % MOD) + //先把两串自身的算上
		  (one[i - 2] % MOD) * (zero[i - 1] % MOD);//（前后关系）拼接后前面的每一个1都与后面的形成逆序
        N[i] %= MOD;
    }
    while (T--) {
        cin >> n;
        cout << N[n] << '\n';
    }
}