DeepSeek LeetCode 3700. 锯齿形数组的总数 II Java实现

题目分析

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