3700. 之字形数组的数量 II

Hard

题目描述

给你三个整数 n、l 和 r。

长度为 n 的之字形数组定义如下：

每个元素都在范围 [l, r] 内
没有两个相邻元素相等
没有三个连续元素形成严格递增或严格递减序列

返回有效之字形数组的总数。

由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

严格递增序列是指每个元素都严格大于前一个元素（如果存在）。

严格递减序列是指每个元素都严格小于前一个元素（如果存在）。

示例 1：

输入：n = 3, l = 4, r = 5

输出：2

解释：

使用范围 [4, 5] 中的值，长度为 n = 3 的有效之字形数组只有 2 个：

[4, 5, 4]
[5, 4, 5]

示例 2：

输入：n = 3, l = 1, r = 3

输出：10

解释：

使用范围 [1, 3] 中的值，长度为 n = 3 的有效之字形数组有 10 个：

[1, 2, 1], [1, 3, 1], [1, 3, 2]
[2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
[3, 1, 2], [3, 1, 3], [3, 2, 3]

所有数组都满足之字形条件。

约束条件：

3 <= n <= 10^9
1 <= l < r <= 75

解题思路

这是一个典型的矩阵快速幂优化的动态规划问题。

核心思路：

首先理解之字形数组的约束：三个连续元素不能严格单调。这意味着如果前两个元素形成上升趋势，第三个元素不能继续上升；如果前两个元素形成下降趋势，第三个元素不能继续下降。

状态定义：

我们需要记录当前位置的值和下一个比较的方向。定义状态为 (value, direction)，其中 direction 表示下一个元素应该相对当前元素的方向：

up: 下一个元素应该大于当前元素
down: 下一个元素应该小于当前元素

状态转移：

设 m = r - l + 1 为可选值的数量。我们用长度为 2m 的向量表示所有状态，前 m 个位置表示 “下一个比较为向下”，后 m 个位置表示 “下一个比较为向上”。

转移规则：

从 up, x 状态可以转移到 down, y，其中 y > x
从 down, x 状态可以转移到 up, y，其中 y < x

矩阵快速幂：

由于 n 可能很大（最大 10^9），我们需要使用矩阵快速幂来优化。构建转移矩阵 T，然后计算 T^(n-1)，最后应用到初始状态向量上。

对于 n = 1 的特殊情况，直接返回 m。

代码实现

class Solution {
public:
    const int MOD = 1000000007;
    
    vector<vector<long long>> multiply(const vector<vector<long long>>& A, const vector<vector<long long>>& B) {
        int n = A.size();
        vector<vector<long long>> C(n, vector<long long>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }
    
    vector<vector<long long>> matrixPower(vector<vector<long long>>& matrix, long long power) {
        int n = matrix.size();
        vector<vector<long long>> result(n, vector<long long>(n, 0));
        for (int i = 0; i < n; i++) result[i][i] = 1;
        
        while (power > 0) {
            if (power & 1) {
                result = multiply(result, matrix);
            }
            matrix = multiply(matrix, matrix);
            power >>= 1;
        }
        return result;
    }
    
    int zigZagArrays(int n, int l, int r) {
        if (n == 1) return r - l + 1;
        
        int m = r - l + 1;
        vector<vector<long long>> T(2 * m, vector<long long>(2 * m, 0));
        
        // Build transition matrix
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < m; y++) {
                if (y > x) {
                    T[m + x][y] = 1; // from up,x to down,y
                }
                if (y < x) {
                    T[x][m + y] = 1; // from down,x to up,y
                }
            }
        }
        
        vector<vector<long long>> Tn = matrixPower(T, n - 1);
        
        long long result = 0;
        for (int i = 0; i < 2 * m; i++) {
            for (int j = 0; j < 2 * m; j++) {
                result = (result + Tn[i][j]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 1000000007
        
        if n == 1:
            return r - l + 1
        
        m = r - l + 1
        
        def multiply(A, B):
            size = len(A)
            C = [[0] * size for _ in range(size)]
            for i in range(size):
                for j in range(size):
                    for k in range(size):
                        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
            return C
        
        def matrix_power(matrix, power):
            size = len(matrix)
            result = [[0] * size for _ in range(size)]
            for i in range(size):
                result[i][i] = 1
            
            while power > 0:
                if power & 1:
                    result = multiply(result, matrix)
                matrix = multiply(matrix, matrix)
                power >>= 1
            return result
        
        # Build transition matrix
        T = [[0] * (2 * m) for _ in range(2 * m)]
        
        for x in range(m):
            for y in range(m):
                if y > x:
                    T[m + x][y] = 1  # from up,x to down,y
                if y < x:
                    T[x][m + y] = 1  # from down,x to up,y
        
        Tn = matrix_power(T, n - 1)
        
        result = 0
        for i in range(2 * m):
            for j in range(2 * m):
                result = (result + Tn[i][j]) % MOD
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    
    private long[,] Multiply(long[,] A, long[,] B) {
        int n = A.GetLength(0);
        long[,] C = new long[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    C[i, j] = (C[i, j] + A[i, k] * B[k, j]) % MOD;
                }
            }
        }
        return C;
    }
    
    private long[,] MatrixPower(long[,] matrix, long power) {
        int n = matrix.GetLength(0);
        long[,] result = new long[n, n];
        for (int i = 0; i < n; i++) result[i, i] = 1;
        
        while (power > 0) {
            if ((power & 1) == 1) {
                result = Multiply(result, matrix);
            }
            matrix = Multiply(matrix, matrix);
            power >>= 1;
        }
        return result;
    }
    
    public int ZigZagArrays(int n, int l, int r) {
        if (n == 1) return r - l + 1;
        
        int m = r - l + 1;
        long[,] T = new long[2 * m, 2 * m];
        
        // Build transition matrix
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < m; y++) {
                if (y > x) {
                    T[m + x, y] = 1; // from up,x to down,y
                }
                if (y < x) {
                    T[x, m + y] = 1; // from down,x to up,y
                }
            }
        }
        
        long[,] Tn = MatrixPower(T, n - 1);
        
        long result = 0;
        for (int i = 0; i < 2 * m; i++) {
            for (int j = 0; j < 2 * m; j++) {
                result = (result + Tn[i, j]) % MOD;
            }
        }
        
        return (int)result;
    }
}

var zigZagArrays = function(n, l, r) {
    const MOD = 1000000007;
    const range = r - l + 1;
    
    if (n == 1) return range % MOD;
    if (n == 2) return (1n * range * (range - 1)) % BigInt(MOD);
    
    // dp[i][0] = ways where last 3 elements are increasing
    // dp[i][1] = ways where last 3 elements are decreasing
    // dp[i][2] = ways where last 3 elements are neither inc nor dec (valid zigzag)
    
    let dp = new Array(3).fill(0n);
    
    // Base case for n=3
    // Total ways to place 3 elements
    let total = 1n * BigInt(range) * BigInt(range - 1) * BigInt(range - 1);
    
    // Invalid ways (strictly increasing)
    let inc = 1n * BigInt(range) * BigInt(Math.max(0, range - 1)) * BigInt(Math.max(0, range - 2)) / 6n;
    if (range >= 3) {
        inc = 1n * BigInt(range) * BigInt(range - 1) * BigInt(range - 2) / 6n;
    } else {
        inc = 0n;
    }
    
    // Invalid ways (strictly decreasing) - same as increasing
    let dec = inc;
    
    dp[0] = inc; // increasing
    dp[1] = dec; // decreasing  
    dp[2] = total - inc - dec; // valid zigzag
    
    if (n == 3) return Number(dp[2] % BigInt(MOD));
    
    // Matrix exponentiation for transitions
    // When we add a new element at position i+1:
    // new_inc = valid_zigzag_ways_where_new_element_makes_increasing
    // new_dec = valid_zigzag_ways_where_new_element_makes_decreasing  
    // new_zigzag = all_other_valid_ways
    
    for (let i = 4; i <= n; i++) {
        let new_inc = dp[1] * BigInt(Math.max(0, range - 2)) % BigInt(MOD);
        let new_dec = dp[0] * BigInt(Math.max(0, range - 2)) % BigInt(MOD);
        let new_zigzag = (dp[2] * BigInt(range - 1) - new_inc - new_dec + BigInt(MOD) + BigInt(MOD)) % BigInt(MOD);
        
        dp[0] = new_inc;
        dp[1] = new_dec;
        dp[2] = new_zigzag;
    }
    
    return Number((dp[0] + dp[1] + dp[2]) % BigInt(MOD));
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(m³ × log n)，其中 m = r - l + 1
空间复杂度	O(m²)

其中矩阵乘法需要 O(m³) 时间，矩阵快速幂需要 O(log n) 次乘法操作。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析