题解 | 斐波那契字符串

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

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

const ll MOD=1e9+7;

struct num
{
	ll cop=0;
	ll one=0;
	ll zero=0;
};

vector<num>dp(1e5+1);

void solve()
{//斐波那契的数据增长速度是非常恐怖的 我们构造出第n个字符串再找逆序对不现实
//但是我们可以从递推的角度来思考 Sn的逆序对数量等于Sn-2的逆序对数量加Sn-1的逆序对数量再加上
//Sn-2中1的数量乘以Sn-1中0的数量 因为Sn=Sn-2+Sn-1 所以Sn-2中的每一个1都能和Sn-1中的每一个0构成逆序对 另外我们还要维护一下每个Sn的1数量和0数量 然后再处理一下dp数组即可
//记得在最开始预处理 不要每次运行测试数据都处理一次 会超时
	int n;
	cin >> n;
	
	cout << dp[n].cop << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	cin >> t;

	dp[1].zero=1,dp[2].one=1;
	for(int i=3;i<=1e5;i++)
	{
		dp[i].cop=(dp[i-2].cop%MOD+dp[i-1].cop%MOD+dp[i-2].one%MOD*dp[i-1].zero%MOD)%MOD;
		dp[i].one=(dp[i-2].one%MOD+dp[i-1].one%MOD)%MOD;
		dp[i].zero=(dp[i-2].zero%MOD+dp[i-1].zero%MOD)%MOD;
	}

	while(t--)
	{
		solve();
	}
	return 0;
}