class Solution {
public:
int idealArrays(int n, int maxValue) {
}
};
2338. 统计理想数组的数目
给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。
对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：
arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109 + 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 解释：存在以下理想数组： - 以 1 开头的数组（9 个）： - 不含其他不同值（1 个）：[1,1,1,1,1] - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2] - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3] - 以 2 开头的数组（1 个）：[2,2,2,2,2] - 以 3 开头的数组（1 个）：[3,3,3,3,3] 共计 9 + 1 + 1 = 11 个不同理想数组。
提示：
2 <= n <= 1041 <= maxValue <= 104原站题解
java 解法, 执行用时: 14 ms, 内存消耗: 43.1 MB, 提交时间: 2023-08-11 10:48:27
// 纯数学解法
class Solution {
static final int MOD = (int) 1e9 + 7, MX = (int) 1e4 + 1, MX_K = 13; // 至多 13 个质因数
static List[] ks = new List[MX]; // ks[x] 为 x 分解质因数后，每个质因数的个数列表
static int[][] c = new int[MX + MX_K][MX_K + 1]; // 组合数
static {
for (var i = 1; i < MX; i++) {
ks[i] = new ArrayList<Integer>();
var x = i;
for (var p = 2; p * p <= x; ++p) {
if (x % p == 0) {
var k = 1;
for (x /= p; x % p == 0; x /= p) ++k;
ks[i].add(k);
}
}
if (x > 1) ks[i].add(1);
}
c[0][0] = 1;
for (var i = 1; i < MX + MX_K; ++i) {
c[i][0] = 1;
for (var j = 1; j <= Math.min(i, MX_K); ++j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
}
public int idealArrays(int n, int maxValue) {
var ans = 0L;
for (var x = 1; x <= maxValue; ++x) {
var mul = 1L;
for (var k : ks[x]) mul = mul * c[n + (int) k - 1][(int) k] % MOD;
ans += mul;
}
return (int) (ans % MOD);
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-08-11 10:47:44
const mod, mx, mxK int = 1e9 + 7, 1e4 + 1, 13 // 至多 13 个质因数
var ks [mx][]int
var c [mx + mxK][mxK + 1]int
func init() {
for i := 2; i < mx; i++ {
x := i
for p := 2; p*p <= x; p++ {
if x%p == 0 {
k := 1
for x /= p; x%p == 0; x /= p {
k++
}
ks[i] = append(ks[i], k)
}
}
if x > 1 {
ks[i] = append(ks[i], 1)
}
}
c[0][0] = 1
for i := 1; i < len(c); i++ {
c[i][0] = 1
for j := 1; j <= mxK && j <= i; j++ {
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
}
}
}
func idealArrays(n, maxValue int) (ans int) {
for _, ks := range ks[1 : maxValue+1] {
mul := 1
for _, k := range ks {
mul = mul * c[n+k-1][k] % mod
}
ans = (ans + mul) % mod
}
return ans
}
python3 解法, 执行用时: 148 ms, 内存消耗: 17 MB, 提交时间: 2023-08-11 10:46:34
MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1
ks = [[] for _ in range(MX)] # ks[x] 为 x 分解质因数后，每个质因数的个数列表
for i in range(2, MX):
p, x = 2, i
while p * p <= x:
if x % p == 0:
k = 1
x //= p
while x % p == 0:
k += 1
x //= p
ks[i].append(k)
p += 1
if x > 1: ks[i].append(1)
class Solution:
def idealArrays(self, n: int, maxValue: int) -> int:
ans = 0
for x in range(1, maxValue + 1):
mul = 1
for k in ks[x]:
mul = mul * comb(n + k - 1, k) % MOD
ans += mul
return ans % MOD