题目分析

LeetCode 3700 是 3699 的困难版本。

两题核心逻辑相同，但数据范围差异巨大：

· 3699 (I)：3 ≤ n ≤ 2000，1 ≤ l < r ≤ 2000 → 可直接 DP
· 3700 (II)：3 ≤ n ≤ 10⁹，1 ≤ l < r ≤ 75 → n 极大，需用矩阵快速幂加速

核心思路

沿用 3699 的 DP 状态：

· up[j]：以值 j 结尾且最后一步为上升的方案数
· down[j]：以值 j 结尾且最后一步为下降的方案数

长度为 1 时：up[j] = down[j] = 1

转移（添加一个新元素）：

· newUp[x] = sum(down[0..x-1]) — 前一步下降且值 < x
· newDown[x] = sum(up[x+1..m-1]) — 前一步上升且值 > x

将 up 和 down 拼接成向量，转移是线性变换，用矩阵快速幂计算 n-1 次转移。

复杂度

· 时间：O(m³ · log n)，m = r-l+1 ≤ 75
· 空间：O(m²)

Java实现

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int zigZagArrays(int n, int l, int r) {
        int m = r - l + 1;          // 值域大小，≤ 75
        int size = 2 * m;           // up + down 拼接

        // 构建转移矩阵 T (size x size)
        long[][] T = new long[size][size];
        for (int i = 0; i < m; i++) {
            // newUp[i] = sum(down[0..i-1])
            for (int j = 0; j < i; j++) {
                T[i][m + j] = 1;    // 第 i 行，down[j] 列
            }
            // newDown[i] = sum(up[i+1..m-1])
            for (int j = i + 1; j < m; j++) {
                T[m + i][j] = 1;    // 第 m+i 行，up[j] 列
            }
        }

        // 初始向量 v：长度为 1 时，up 和 down 全为 1
        long[] v = new long[size];
        for (int i = 0; i < size; i++) {
            v[i] = 1;
        }

        // 计算 T^(n-1) * v
        long[][] power = matrixPow(T, n - 1);
        long[] result = matrixMulVec(power, v);

        // 答案 = sum(up) + sum(down)
        long ans = 0;
        for (long val : result) {
            ans = (ans + val) % MOD;
        }
        return (int) ans;
    }

    // 矩阵快速幂
    private long[][] matrixPow(long[][] base, int exp) {
        int n = base.length;
        long[][] res = new long[n][n];
        for (int i = 0; i < n; i++) {
            res[i][i] = 1;
        }
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = matrixMul(res, base);
            }
            base = matrixMul(base, base);
            exp >>= 1;
        }
        return res;
    }

    // 矩阵乘法 (取模)
    private long[][] matrixMul(long[][] A, long[][] B) {
        int n = A.length;
        long[][] C = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                if (A[i][k] == 0) continue;
                long aik = A[i][k];
                for (int j = 0; j < n; j++) {
                    C[i][j] = (C[i][j] + aik * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    // 矩阵 × 向量 (取模)
    private long[] matrixMulVec(long[][] A, long[] v) {
        int n = A.length;
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = 0; j < n; j++) {
                sum = (sum + A[i][j] * v[j]) % MOD;
            }
            res[i] = sum;
        }
        return res;
    }
}
```

示例验证

示例 1：n=3, l=4, r=5 → 输出 2（[4,5,4] 和 [5,4,5]）

示例 2：n=3, l=1, r=3 → 输出 10