题解 | 斐波那契字符串

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/6
 * @description BGN61 斐波那契字符串
 */
public class Main {

    public static int[][] cache = new int[100005][3];
    public static boolean[] visit = new boolean[100005];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int k = in.nextInt();
            int[] a = new int[3];
            dfs(k, a);
            System.out.println(a[2]);
        }
    }
    //a[0] 0的数量, a[1] 1的数量, a[2] 逆序对数量
    public static void dfs(int n, int[] a) {
        if (n == 1) {
            a[0] = 1;
            a[1] = 0;
            a[2] = 0;
        } else if (n == 2) {
            a[0] = 0;
            a[1] = 1;
            a[2] = 0;
        } else if (n > 2) {
            if (visit[n]) {
                System.arraycopy(cache[n], 0, a, 0, 3);
                return;
            }
            dfs(n - 1, a);
            int[] b = new int[3];
            //System.arraycopy(a, 0, b, 0, 3);
            dfs(n - 2, b);

            int base = (int)1e9 + 7;
            a[2] = (int) ((a[2] + b[2] + (long) a[0] * b[1]) % base);
            a[0] = (a[0] + b[0]) % base;
            a[1] = (a[1] + b[1]) % base;
            System.arraycopy(a, 0, cache[n], 0, 3);
            visit[n] = true;
        }
    }
}
//1. 清楚递归流程 
//2. 然后需要对递归使用记忆化搜索进行优化, 从o(2 ^ n)变为o(n)，注意这是一个后续遍历
//3. 注意精度 
//4. 参数使用引用注意int[] b = new int[3]; 也可以使用public static int[] dfs(int n)