题解 | 斐波那契字符串

这一题很有意思，它不能直接构造那个字符串，会爆内存

我们应当根据题意去考虑要用到哪些性质，以此不构造也把这题做出来

首先就是，我们应当统计每一个字符串中1的个数，0的个数

统计方法使用dp，也就是前两个相加，注意，这里每一次加完后都要进行取模，以防止溢出

然后我们就要计算符合条件的逆序对数量，我这里用ans数组表示

根据题意，逆序对应当包括三个部分，首先是i-1和i-2这两个字符串本身的ans相加，其次就是由于这两个字符串拼接以后而多出来的逆序对，这是由one[i-2]*zero[i-1]组成。将这些加起来就是我们要的逆序对数量

最后输出即可

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner =new Scanner(System.in);
		long t=scanner.nextLong();
		long len[]=new long[100005];
		long one[]=new long[100005];
		long zero[]=new long[100005];
		long ans[]=new long[100005];
		len[1]=1;
		len[2]=1;
		one[1]=0;
		one[2]=1;
		zero[1]=1;
		zero[2]=0;
		for (int i = 3; i < ans.length; i++) {
			len[i]=(len[i-1]+len[i-2])%(long)(1e9+7);
			one[i]=(one[i-1]+one[i-2])%(long)(1e9+7);
			zero[i]=(zero[i-1]+zero[i-2])%(long)(1e9+7);
			ans[i]=(ans[i-1]+ans[i-2]+one[i-2]*zero[i-1])%(long)(1e9+7);
		}
		while(t-->0) {
			int n=scanner.nextInt();
			System.out.println(ans[n]);
		}
		
		

	}

}