千问 LeetCode 2338.统计理想数组的数目 public int idealArrays(int n, int maxValue)
这道题是 LeetCode 2338 题，是一道非常经典的组合数学 + 质因数分解问题。如果直接使用动态规划（DP）暴力求解，会因时间复杂度过高而超时。我们需要透过“整除”这个条件，挖掘其背后的数学规律。
题目解析
理想数组需要满足：
1. 数组中的每个数都在 [1, maxValue] 范围内。
2. 每个 arr[i] 都能被 arr[i-1] 整除（即 arr[i] % arr[i-1] == 0）。
由条件2可知，数组一定是非递减的。我们可以换个角度思考：枚举理想数组的最后一个数（最大值）。
假设理想数组的最后一个数是 x。
1. 分解质因数：将 x 分解质因数，假设 x = p1^k1 * p2^k2 * ...。
2. 分配质因数：数组从第一个数（最小为1）演变到最后一个数 x，本质上就是把 x 的所有质因数，一步步“分配”到数组的 n 个位置上。由于数组是非递减的，质因数只能“增加”不能“减少”。
对于某一个质因数 p，假设它在 x 中出现了 k 次（即 p^k），我们需要把这 k 个 p 分配到 n 个位置上。这就变成了一个经典的隔板法问题：把 k 个相同的小球放入 n 个不同的盒子中，允许盒子为空，有多少种放法？
公式为：C(n + k - 1, k)。
3. 计算总数：对于数 x，它的总方案数就是它所有质因数的分配方案数的乘积。最后，我们将 1 到 maxValue 所有数字作为结尾的方案数累加，就是最终答案。
为什么不会超时？
因为 maxValue 最大为 10^4，而 2^14 > 10^4，所以任何一个数的质因数总个数最多只有 13 个左右。这使得组合数的计算非常快。
Java 代码实现
class Solution {
private static final int MOD = 1000000007;
// 10^4 以内的数，质因数个数最多不超过 14 个 (2^14 > 10000)
private static final int MAX_K = 14;
public int idealArrays(int n, int maxValue) {
// 1. 预处理组合数 C(i, j)，使用杨辉三角递推公式：C(i, j) = C(i-1, j) + C(i-1, j-1)
// 我们需要计算 C(n + k - 1, k)，i 最大约为 n + 14
long[][] c = new long[n + MAX_K + 1][MAX_K + 1];
for (int i = 0; i 1，说明还有一个大于 sqrt(x) 的质因数，个数为 1
if (temp > 1) {
ways = (ways * c[n][1]) % MOD;
}
ans = (ans + ways) % MOD;
}
return (int) ans;
}
}
复杂度分析
* 时间复杂度：O(maxValue * sqrt(maxValue) + n * MAX_K)。预处理组合数为 O(n)，枚举每个数并分解质因数最坏是 O(sqrt(maxValue))。由于 MAX_K 极小，整体运行效率非常高。
* 空间复杂度：O(n * MAX_K)，主要用于存储预处理的组合数表。
这种解法完美避开了暴力 DP 的超时陷阱，利用数学性质将问题转化为了高效的组合数计算。如果有任何步骤不理解，随时可以问我！