Hard

题目描述

给你两个整数 n 和 maxValue，用来描述一个理想数组。

对于下标从 0 开始、长度为 n 的整数数组 arr，如果满足以下条件，则认为该数组是一个 理想数组：

  • 每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n。
  • 每个 arr[i] 都能被 arr[i - 1] 整除，其中 0 < i < n。

返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 10^9 + 7 取余的结果。

示例 1：

输入：n = 2, maxValue = 5
输出：10
解释：以下是可能的理想数组：
- 以值 1 开始的数组（5 个数组）：[1,1], [1,2], [1,3], [1,4], [1,5]
- 以值 2 开始的数组（2 个数组）：[2,2], [2,4] 
- 以值 3 开始的数组（1 个数组）：[3,3]
- 以值 4 开始的数组（1 个数组）：[4,4]
- 以值 5 开始的数组（1 个数组）：[5,5]
总共有 5 + 2 + 1 + 1 + 1 = 10 个不同的理想数组。

示例 2：

输入：n = 5, maxValue = 3
输出：11

提示：

  • 2 <= n <= 10^4
  • 1 <= maxValue <= 10^4

解题思路

这是一道结合动态规划和组合数学的题目。关键观察是理想数组必须是非递减的，且相邻元素存在整除关系。

核心思路：

  1. 转化问题：我们可以将问题转化为计算严格递增序列的方案数，然后通过组合数学扩展到允许相同元素的情况。

  2. 动态规划：定义 dp[i][k] 表示以数字 i 结尾、长度为 k 的严格递增理想序列的数目。状态转移为：对于每个能被 i 整除的数字 j，有 dp[i][k] += dp[j][k-1]。

  3. 组合数学扩展：对于一个长度为 k 的严格递增序列，我们可以通过在序列中插入重复元素来构造长度为 n 的非严格递增序列。这相当于将 n-k 个相同元素分配到 k 个位置，方案数为 C(n-1, k-1)。

  4. 预处理优化：

    • 预计算所有数字的倍数关系
    • 预计算组合数 C(n-1, k-1)，其中 k 从 1 到 n

算法步骤：

  1. 预处理每个数字的倍数列表
  2. 用DP计算所有严格递增理想序列
  3. 对于每种长度，用组合数计算最终答案

时间复杂度主要由DP部分决定，为 O(maxValue × n × 平均倍数个数)。

代码实现

class Solution {
public:
    int idealArrays(int n, int maxValue) {
        const int MOD = 1e9 + 7;
        
        // 预计算组合数 C(n-1, k-1)
        vector<vector<long long>> C(n, vector<long long>(n, 0));
        for (int i = 0; i < n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
        
        // dp[i][k] 表示以数字i结尾、长度为k的严格递增序列数目
        vector<vector<long long>> dp(maxValue + 1, vector<long long>(n + 1, 0));
        
        // 初始化：长度为1的序列
        for (int i = 1; i <= maxValue; i++) {
            dp[i][1] = 1;
        }
        
        // DP计算严格递增序列
        for (int k = 2; k <= n; k++) {
            for (int i = 1; i <= maxValue; i++) {
                // 找到所有能被i整除的数字j
                for (int j = 1; j * j <= i; j++) {
                    if (i % j == 0) {
                        dp[i][k] = (dp[i][k] + dp[j][k-1]) % MOD;
                        if (j != i / j) {
                            dp[i][k] = (dp[i][k] + dp[i/j][k-1]) % MOD;
                        }
                    }
                }
            }
        }
        
        // 统计答案
        long long result = 0;
        for (int i = 1; i <= maxValue; i++) {
            for (int k = 1; k <= n; k++) {
                if (dp[i][k] > 0) {
                    result = (result + dp[i][k] * C[n-1][k-1]) % MOD;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        MOD = 10**9 + 7
        
        # 预计算组合数 C(n-1, k-1)
        C = [[0] * n for _ in range(n)]
        for i in range(n):
            C[i][0] = 1
            for j in range(1, i + 1):
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
        
        # dp[i][k] 表示以数字i结尾、长度为k的严格递增序列数目
        dp = [[0] * (n + 1) for _ in range(maxValue + 1)]
        
        # 初始化：长度为1的序列
        for i in range(1, maxValue + 1):
            dp[i][1] = 1
        
        # DP计算严格递增序列
        for k in range(2, n + 1):
            for i in range(1, maxValue + 1):
                # 找到所有能被i整除的数字j
                j = 1
                while j * j <= i:
                    if i % j == 0:
                        dp[i][k] = (dp[i][k] + dp[j][k-1]) % MOD
                        if j != i // j:
                            dp[i][k] = (dp[i][k] + dp[i//j][k-1]) % MOD
                    j += 1
        
        # 统计答案
        result = 0
        for i in range(1, maxValue + 1):
            for k in range(1, n + 1):
                if dp[i][k] > 0:
                    result = (result + dp[i][k] * C[n-1][k-1]) % MOD
        
        return result

public class Solution {
    public int IdealArrays(int n, int maxValue) {
        const int MOD = 1000000007;
        
        // 预计算组合数 C(n-1, k-1)
        long[,] C = new long[n, n];
        for (int i = 0; i < n; i++) {
            C[i, 0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i, j] = (C[i-1, j-1] + C[i-1, j]) % MOD;
            }
        }
        
        // dp[i][k] 表示以数字i结尾、长度为k的严格递增序列数目
        long[,] dp = new long[maxValue + 1, n + 1];
        
        // 初始化：长度为1的序列
        for (int i = 1; i <= maxValue; i++) {
            dp[i, 1] = 1;
        }
        
        // DP计算严格递增序列
        for (int k = 2; k <= n; k++) {
            for (int i = 1; i <= maxValue; i++) {
                // 找到所有能被i整除的数字j
                for (int j = 1; j * j <= i; j++) {
                    if (i % j == 0) {
                        dp[i, k] = (dp[i, k] + dp[j, k-1]) % MOD;
                        if (j != i / j) {
                            dp[i, k] = (dp[i, k] + dp[i/j, k-1]) % MOD;
                        }
                    }
                }
            }
        }
        
        // 统计答案
        long result = 0;
        for (int i = 1; i <= maxValue; i++) {
            for (int k = 1; k <= n; k++) {
                if (dp[i, k] > 0) {
                    result = (result + dp[i, k] * C[n-1, k-1]) % MOD;
                }
            }
        }
        
        return (int)result;
    }
}

var idealArrays = function(n, maxValue) {
    const MOD = 1000000007;
    
    // Precompute factorials and inverse factorials for combinations
    const fact = new Array(n + 1);
    const inv_fact = new Array(n + 1);
    fact[0] = 1;
    for (let i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    
    const pow = (base, exp, mod) => {
        let result = 1;
        while (exp > 0) {
            if (exp % 2 === 1) result = (result * base) % mod;
            base = (base * base) % mod;
            exp = Math.floor(exp / 2);
        }
        return result;
    };
    
    inv_fact[n] = pow(fact[n], MOD - 2, MOD);
    for (let i = n - 1; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
    
    const C = (n, r) => {
        if (r > n || r < 0) return 0;
        return (fact[n] * inv_fact[r] % MOD) * inv_fact[n - r] % MOD;
    };
    
    // Find all multiples for each number
    const multiples = new Array(maxValue + 1);
    for (let i = 1; i <= maxValue; i++) {
        multiples[i] = [];
        for (let j = i * 2; j <= maxValue; j += i) {
            multiples[i].push(j);
        }
    }
    
    // dp[i][j] = number of ways to have an ideal array of length i ending with value j
    let dp = new Array(maxValue + 1).fill(0);
    let newDp = new Array(maxValue + 1).fill(0);
    
    // Initialize: arrays of length 1
    for (let j = 1; j <= maxValue; j++) {
        dp[j] = 1;
    }
    
    // For each additional length
    for (let len = 2; len <= n; len++) {
        newDp.fill(0);
        for (let prev = 1; prev <= maxValue; prev++) {
            if (dp[prev] === 0) continue;
            // Can stay at the same value
            newDp[prev] = (newDp[prev] + dp[prev]) % MOD;
            // Can go to any multiple
            for (const next of multiples[prev]) {
                newDp[next] = (newDp[next] + dp[prev]) % MOD;
            }
        }
        [dp, newDp] = [newDp, dp];
    }
    
    let result = 0;
    for (let j = 1; j <= maxValue; j++) {
        result = (result + dp[j]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析结果
时间复杂度O(n² + maxValue × n × √maxValue)
空间复杂度O(n² + maxValue × n)

其中组合数预处理需要 O(n²) 时间，DP部分对每个数字和长度，需要枚举其所有因子，平均复杂度为 O(√maxValue)。

相关题目