题解 | 斐波那契字符串-Java

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;
    static final int MAX_N = 100000;
    static long[] len = new long[MAX_N + 1];   // 存储S_n的长度
    static long[] cnt1 = new long[MAX_N + 1];  // 存储S_n中'1'的数量
    static long[] inv = new long[MAX_N + 1];   // 存储S_n中逆序对的数量

    // 静态初始化块，预处理所有需要的数据
    static {
        // 初始化长度数组
        len[1] = 1;
        len[2] = 1;
        for (int i = 3; i <= MAX_N; i++) {
            len[i] = (len[i - 2] + len[i - 1]) % MOD;
        }

        // 初始化'1'的数量数组
        cnt1[1] = 0;  // S₁是"0"，没有'1'
        cnt1[2] = 1;  // S₂是"1"，有1个'1'
        for (int i = 3; i <= MAX_N; i++) {
            cnt1[i] = (cnt1[i - 2] + cnt1[i - 1]) % MOD;
        }

        // 初始化逆序对数量数组
        inv[1] = 0;  // S₁中没有逆序对
        inv[2] = 0;  // S₂中没有逆序对
        for (int i = 3; i <= MAX_N; i++) {
            // 逆序对 = 前两部分的逆序对 + 跨部分的新逆序对
            inv[i] = (inv[i - 2] + inv[i - 1]) % MOD;

            // 计算S_{i-1}中'0'的数量
            long cnt0 = (len[i - 1] - cnt1[i - 1] + MOD) % MOD;

            // 跨部分的逆序对数量 = S_{i-2}中'1'的数量 * S_{i-1}中'0'的数量
            long cross = (cnt1[i - 2] * cnt0) % MOD;
            inv[i] = (inv[i] + cross) % MOD;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        // 处理每组测试数据
        while (T-- > 0) {
            int n = sc.nextInt();
            System.out.println(inv[n]);
        }

        sc.close();
    }
}