统计理想数组的数目

标签: 数学 动态规划 组合数学 数论

难度: Hard

给你两个整数 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 <= 104
  • 1 <= maxValue <= 104

Submission

运行时间: 77 ms

内存: 17.1 MB

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

Explain

此题解采用数学组合学和质因数分解的方法。首先，预处理计算1到maxValue之间每个整数的质因数分解情况，并记录每个质因数的个数。核心思想是计算每个数字作为数组起始元素时，可以形成多少个符合条件的理想数组。对于每个数x，根据其质因数的分解，利用组合公式计算以x开始且满足条件的数组个数。组合公式 comb(n + k - 1, k) 用于计算添加 k 个相同的数到长度为 n 的序列的方法数，其中 n 为原序列长度。对于数组中的每个数，可以视为序列中增加了该数的质因数的个数，因此应用上述组合公式。最后将所有计算结果累加得到答案。

时间复杂度: O(maxValue * (sqrt(maxValue) + n))

空间复杂度: O(maxValue * log(maxValue) + n)

MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1
ks = [[] for _ in range(MX)]  # 每个数的质因数的次数列表
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  # 返回结果取模

Explore

组合公式`comb(n + k - 1, k)`代表的是从`n + k - 1`个位置中选择`k`个位置的组合数，这在数学中也称为'带重复的组合问题'。在这个问题中，将一个数的质因数看作是不可区分的物品，数组的长度看作是`n`个不同的盒子，问题转化为将这些不可区分的物品放入不同的盒子中的方法数。比如，一个数的某个质因数出现了`k`次，那么问题就变成了在`n`个不同的位置上填充这`k`个相同的质因数，可以用这个组合公式来计算。

在质因数分解的过程中，如果在内层循环结束后`x`仍大于1，这意味着`x`是一个质数，因为所有小于`x`的质因数已经被除尽。此时`x`本身就是一个质因数，且未在循环中被分解，因此其计数应该为1。这一步骤确保了每一个大于1的余数都被认为是其本身的质因数，且出现次数为1。

在题解中，`ks[x]`记录了数字`x`的所有质因数的次数。对于每一个质因数的次数`k`，通过计算`comb(n + k - 1, k)`来得出将这个质因数`k`次放入`n`个不同位置的方法数。循环遍历每个质因数确保考虑了所有质因数的组合方式。最终，这些组合数的乘积给出了以`x`为起始值的理想数组的数目。通过乘积操作，我们实际上是在计算多个质因数组合在一起的总方法数，从而确保了所有可能的组合都被计算在内。因此，该循环能够正确计算所有理想数组的数目，不会漏掉任何组合。