LeetCode 解題筆記：3700. Number of ZigZag Arrays II

作者：王一哲
日期：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;

C++ 程式碼

Runtime: 838 ms, beats 41.86%. Memory: 73.04 MB, beats 20.93%.

typedef long long LL;
const int MOD = 1000000007;  // 取餘數用的超大質數
typedef vector<vector<LL>> Matrix;  // 二維 vector

class Solution {
public:
    // 矩陣乘法
    Matrix matmul(const Matrix& A, const Matrix& B, int size) {
        Matrix C (size, vector<LL> (size, 0));
        for(int i = 0; i < size; i++) {
            for(int k = 0; k < size; k++) {
                if (A[i][k] == 0) continue;  // 0，不需要乘
                for(int j = 0; j < size; j++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    // 矩陣快速冪，計算 A**p
    Matrix matpow(Matrix A, int p, int size) {
        Matrix C (size, vector<LL> (size, 0));  // 計算結果
        for(int i = 0; i < size; i++) C[i][i] = 1;  // 單位矩陣
        while(p > 0) {
            if (p&1) C = matmul(C, A, size);
            A = matmul(A, A, size);
            p >>= 1;
        }
        return C;
    }

    int zigZagArrays(int n, int l, int r) {
        int k = r - l + 1;  // ，可選的數字數量
        
        // 特例，k == 1，無法排出之字形的陣列，回傳 0
        if (k == 1) return 0;

        // 矩陣維度
        int size = 2 * k;

        // 初始化，長度 2 的狀態，up 儲存在 stata[0] ~ state[k-1]
        // down 儲存在 stata[k] ~ state[2*k - 1]
        vector<LL> state (size, 0);
        for(int v = 0; v < k; v++) {
            state[v] = v;  // up，有 v 個數字小於 v
            state[k+v] = k-1-v;  // down，有 (k-1) - v 個數字大於 v
        }

        // 特例，n = 2
        if (n == 2) {
            LL ans = 0;
            for(int i = 0; i < size; i++) ans = (ans + state[i]) % MOD;
            return ans;
        }

        // 轉移矩陣
        Matrix M (size, vector<LL> (size, 0));
        for(int v = 0; v < k; v++) {
            // up[v] 等於上一輪的 sum(down[0], ..., down[v-1])
            for(int u = 0; u < v; u++) {
                M[v][k+u] = 1;
            }
            // down[v] 等於上一輪的 sum(up[0], ..., up[v-1])
            for(int u = v+1; u < k; u++) {
                M[k+v][u] = 1;
            }
        }

        // 計算 M**(n-2)
        Matrix M_n2 = matpow(M, n-2, size);
        
        // 將 M**(n-2) 乘上初始向量 state，得到最終向量 final_state
        vector<LL> final_state (size, 0);
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                final_state[i] = (final_state[i] + M_n2[i][j] * state[j]) % MOD;
            }
        }

        // 將 final_state 的所有元素加總即為答案
        LL ans = 0;
        for(int i = 0; i < size; i++) {
            ans = (ans + final_state[i]) % MOD;
        }
        return ans;
    }
};