日期：2026年6月24日
LeetCode 題目連結：3700. Number of ZigZag Arrays II
解題想法
困難題。這題雖然看起來與 3699. Number of ZigZag Arrays I 幾乎一樣，但是測資範圍不同。3699 的測資是 $3 \leq n \leq 2000$, $1 \leq l < r \leq 2000$，3700 的測資是 $3 \leq n \leq 10^9$, $1 \leq l < r \leq 75$，3700 這題的數字量 $n$ 大很多，但是每個數字的範圍 $l, r$ 小很多，因此這題如果用 DP 解題會超時，要改用矩陣快速冪。
Python 程式碼
Runtime: 13213 ms, beats 13.79%. Memory: 21.00 MB, beats 41.38%.
MOD = 10**9 + 7 # 取餘數用的超大質數
class Solution:
# --- 矩陣乘法 ---
def matmul(self, A, B, size):
C = [[0] * size for _ in range(size)]
for i in range(size):
for k in range(size):
if A[i][k] == 0: continue # 0，不需要乘
for j in range(size):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
return C
# --- 矩陣快速冪，計算 A**p ---
def matpow(self, A, p, size):
C = [[0] * size for _ in range(size)] # 計算結果
for i in range(size): C[i][i] = 1 # 單位矩陣
while p:
if p&1: C = self.matmul(C, A, size)
A = self.matmul(A, A, size)
p >>= 1
return C
def zigZagArrays(self, n: int, l: int, r: int) -> int:
k = r - l + 1 # 可選的數字數量
# --- 特例，k == 1，無法排出之字形的陣列，回傳 0 ---
if k == 1: return 0
# 矩陣維度
size = 2 * k
# --- 初始化，長度 2 的狀態，up 儲存在 stata[0] ~ state[k-1] ---
# down 儲存在 stata[k] ~ state[2*k - 1]
state = [0] * size
for v in range(k):
state[v] = v # up，有 v 個數字小於 v
state[k+v] = k-1-v # down，有 (k-1) - v 個數字大於 v
# --- 特例，n = 2 ---
if n == 2:
ans = 0
for i in range(size): ans = (ans + state[i]) % MOD
return ans
# --- 轉移矩陣 ---
M = [[0] * size for _ in range(size)]
for v in range(k):
# up[v] 等於上一輪的 sum(down[0], ..., down[v-1])
for u in range(v): M[v][k+u] = 1
# down[v] 等於上一輪的 sum(up[0], ..., up[v-1])
for u in range(v+1, k): M[k+v][u] = 1
# --- 計算 M**(n-2) ---
M_n2 = self.matpow(M, n-2, size)
# --- 將 M**(n-2) 乘上初始向量 state，得到最終向量 final_state ---
final_state = [0] * size
for i in range(size):
for j in range(size):
final_state[i] = (final_state[i] + M_n2[i][j] * state[j]) % MOD
# --- 將 final_state 的所有元素加總即為答案 ---
ans = 0
for i in range(size): ans = (ans + final_state[i]) % MOD
return ans;
