点击获取AI摘要

2338. 统计理想数组的数目 H

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

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

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

返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109+710^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
解释：存在以下理想数组：

  • 以 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 <= 10410^4

  • 1 <= maxValue <= 10410^4

问题分析

注意到：

  • 任意理想数组 ai{a_i} 满足 1≤a0∣a1∣⋯∣an−1=y, ai≤maxValue1\le a_0\mid a_1\mid\cdots\mid a_{n-1}= y,\text{ }a_i\le \text{maxValue} 。

  • 对于固定的末尾值 y≤maxValuey\le\mathrm{maxValue}，从 1 变到 yy 的“除数链”可看作在每个质因数方向上“累积指数”的过程（把它的每个质因子 pp、指数 epe_p 看成要在前 n−1n-1 个“空位”中放 epe_p 个“乘 pp”操作）。

  • 若 y=∏pieiy=\prod p_i^{e_i}，则在长度为 nn 的链中，需要分配这 eie_i 次“乘以 pip_i”操作到 n−1n-1 个相邻位置上，属于 「Stars and Bars」 模型（ “星星与条纹” ），每种质因子独立，所以总方案数是：

    #{链数}=∏i((n−1)+eiei).\#\{\text{链数}\}=\prod_i\binom{(n-1)+e_i}{e_i}.

  • 最后对所有 yy 累加，并对 109+710^9+7 取模，因此，答案就是

    ∑y=1maxValue[∏pe∥y((n−1)+ee)]mod(109+7).\sum_{y=1}^\mathrm{maxValue}\left[\prod_{p^e\|y}\binom{(n-1)+e}{e}\right]\mathrm{mod}(10^9+7).

预处理 → 枚举 y=1…maxValue → 分解 y 的质因子 → 用“comb”累乘 → 累加取模 → 返回

算法思路

  1. 预处理阶乘与逆元阶乘，支持快速计算组合数 (ab)\binom{a}{b}。
  2. 用 线性／筛法（SPF 最小质因子）对 [1…maxValue][1\ldots\mathrm{maxValue}] 做一次质因数分解，整体复杂度约 O(maxValuelog⁡log⁡maxValue)O(\mathrm{maxValue}\log\log \mathrm{maxValue})。
  3. 对每个 yy 枚举其质因数指数 eie_i，累乘组合数即可。

时间复杂度

  • 阶乘 & 逆元：O(n+log⁡maxValue)O(n + \log \mathrm{maxValue})
  • SPF 筛：O(max⁡Valuelog⁡log⁡maxValue)O(\max\mathrm{Value}\log\log\mathrm{maxValue})
  • 主循环：每个 yy 仅分解一次，总体 O(max⁡Valuelog⁡maxValue)O(\max\mathrm{Value}\log\mathrm{maxValue})
  • 总体：O(n+max⁡Valuelog⁡log⁡maxValue+max⁡Valuelog⁡maxValue)O(n+\max\mathrm{Value}\log\log\mathrm{maxValue}+\max\mathrm{Value}\log\mathrm{maxValue}) ，低于DP

空间复杂度：O(n+max⁡Value)O(n+\max\mathrm{Value}) ，主要用于阶乘数组与 SPF 数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import math
class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        MOD = 10**9 + 7

        # —— 1. 预处理：阶乘 & 逆阶乘 —— 
        # 最大可能的指数增量 ≈ log2(maxValue)
        maxE = int(math.log2(maxValue)) + 1
        up = n - 1 + maxE
        fact = [1] * (up + 1)
        invfact = [1] * (up + 1)
        for i in range(1, up + 1):
            fact[i] = fact[i-1] * i % MOD
        invfact[up] = pow(fact[up], MOD-2, MOD)
        for i in range(up, 0, -1):
            invfact[i-1] = invfact[i] * i % MOD

        def comb(a: int, b: int) -> int:
            if b < 0 or b > a: 
                return 0
            return fact[a] * invfact[b] % MOD * invfact[a-b] % MOD

        # —— 2. SPF 最小质因子筛 —— 
        spf = list(range(maxValue + 1))
        for p in range(2, int(maxValue**0.5) + 1):
            if spf[p] == p:
                for j in range(p*p, maxValue + 1, p):
                    if spf[j] == j:
                        spf[j] = p

        # —— 3. 主循环：对每个 y 分解、累乘组合数 —— 
        ans = 0
        for y in range(1, maxValue + 1):
            ways = 1
            v = y
            while v > 1:
                p = spf[v]
                e = 0
                while v % p == 0:
                    v //= p
                    e += 1
                # 在 n-1 个间隔里放置 e 次“乘 p”操作
                ways = ways * comb((n-1) + e, e) % MOD
            ans = (ans + ways) % MOD

        return ans

另看到题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        MOD = 10**9 + 7

        # —— 1. 预处理：组合数 Pascal 三角 —— 
        maxE = int(math.log2(maxValue)) + 1
        up = n - 1 + maxE
        C = [[0] * (maxE + 1) for _ in range(up + 1)]
        for i in range(up + 1):
            C[i][0] = 1
            for j in range(1, min(i, maxE) + 1):
                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD

        # —— 2. 预处理：EXP 质因子指数列表 —— 
        EXP = [[] for _ in range(maxValue + 1)]
        for y in range(2, maxValue + 1):
            v = y
            p = 2
            while p * p <= v:
                e = 0
                while v % p == 0:
                    v //= p
                    e += 1
                if e:
                    EXP[y].append(e)
                p += 1
            if v > 1:
                EXP[y].append(1)

        # —— 3. 主循环：对每个 y 累乘组合数 —— 
        ans = 0
        for y in range(1, maxValue + 1):
            ways = 1
            for e in EXP[y]:
                ways = ways * C[n - 1 + e][e] % MOD
            ans = (ans + ways) % MOD

        return ans

  1. DP 转组合：把「每一步都要保持可整除」的递推，转化为「质因子指数如何在 nn 个位置上非负分配」的组合计数；
  2. 枚举：对每个可能的末尾值 xx 计算它的组合数贡献，再求和。

  • 对于固定的 yy，它的每个质因子 pp 在 a0,…,an−1a_0,\dots,a_{n-1} 中的指数序列

    e0=0(不一定为0)≤e1≤⋯≤en−1=E,e_0=0(\text{不一定为0})\le e_1\le\cdots\le e_{n−1}=E,

    且 ∑\sum 个位置上的“增加量”恰好等于 EE （ e1+e2+...+ek=Ee_1 + e_2 + ... + e_k = E ）（即 yy 中该质因子的总指数）。

  • “星星与条纹”：前文已解释

  • 实现

    • 预处理每个 x≤maxValuex≤\text{maxValue} 的质因数指数列表，EXP[x] 存放 xx 分解后，每个质因子的指数 [e1,e2,… ][e_1,e_2,\dots]。
    • 预计算组合数 (Nk)\binom{N}{k}：由于 n≤104n\le10^4, 指数 EpE_p 也最多 log⁡2(104)≈14\log_2(10^4)\approx14，我们只需算到 N=n+14−1N=n+14-1。
      用帕斯卡三角，这样 C[N][k] 就是 (Nk) mod (109+7)\binom{N}{k}\bmod(10^9+7)。
    • 枚举所有 x=1…maxValuex=1…maxValue，累加它们作为数组末尾的方案数，注意 x=1x=1 时 EXP[1] 为空，res=1，对应 “全 1 数组” 这一类。

  • 复杂度：

    • 质因数分解：∑x=1Mx=O(M3/2)\sum_{x=1}^{M}\sqrt{x}=O(M^{3/2})，这里 M=maxValue≤104M=\text{maxValue}\le10^4 足够快。
    • 组合数预处理：O((n+max⁡E)×max⁡E)≈O(n⋅log⁡M)O\bigl((n+\max E)\times \max E\bigr)\approx O(n\cdot\log M)。
    • 枚举累加：O(M×(平均质因子数))≈O(Mlog⁡M)O\bigl(M\times (\text{平均质因子数})\bigr)\approx O(M\log M)。
特性 第一个实现（阶乘 + 逆元 comb + SPF 筛分解） 第二个实现（Pascal 组合表 + 试除分解）
组合数计算 预计算 fact 和 invfact 数组，用公式
(ab)=fact[a]fact[b]×fact[a−b]mod  p\binom{a}{b} = \frac{\text{fact}[a]}{\text{fact}[b] \times \text{fact}[a - b]} \mod p 每次 O(1)O(1) 快速计算		 用帕斯卡三角预计算 C[i][j]=(ij)C[i][j] = \binom{i}{j}
查询时直接 O(1)O(1) 取表
质因子分解 先用线性/埃氏思路构造 SPF（最小质因子）表 spf[i]spf[i]
分解时不断 v//=spf[v]v //= spf[v]，复杂度约 O(log⁡v)O(\log{v})		 每个 xx 用试除法 x\sqrt{x} 搜索素因子，累计其指数
预处理时间 构造 fact, invfact：O(n+max⁡E)O(n + \max E)（再加一次快速幂取逆） 构造 SPF：O(Mlog⁡log⁡M)O(M \log \log M) 构造 CC 表：O((n+max⁡E)×max⁡E)O\bigl((n + \max E) \times \max E\bigr)
试除分解：∑x=1MO(x)≈O(M3/2)\sum_{x=1}^M O(\sqrt{x}) \approx O(M^{3/2})
空间开销 两个长度 n+max⁡En + \max E 的数组 + 一个长度 MM 的 SPF 数组 CC 表大约 (n+max⁡E)×(max⁡E)(n + \max E) \times (\max E) 个整数
适用场景 当 max⁡Value\max{Value} 更大（比如 10510^5 、10610^6） 时，SPF 分解会更快、更稳，阶乘逆元计算组合数也更节省空间 n,max⁡Value≤104n, \max{Value} \le 10^4 都较小，预先填表和试除都能在 1–2s 内完成
代码复杂度 略微复杂一些，需要处理逆元和 SPF 数组 直观易懂，组合表和试除都很朴素

Qwen QWQ 32b给出的解，思路大致相同
(预处理最小质因数 → 质因数分解存储 → 阶乘与逆元预计算 → DP到组合数学 → 前缀和优化)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        MOD = 10**9 + 7
        t = n - 1
        if t == 0:
            return maxValue % MOD
        
        max_num = maxValue
        
        # 步骤 1：计算筛的 min_prime 数组.
        min_prime = [0] * (max_num + 1)
        for i in range(2, max_num + 1):
            if min_prime[i] == 0:
                min_prime[i] = i
                for j in range(i*i, max_num+1, i):
                    if min_prime[j] == 0:
                        min_prime[j] = i
        
        # 预计算 factor_list[m]：从质数到指数的字典.
        factor_list = [{} for _ in range(max_num + 1)]
        
        for m in range(2, max_num + 1):
            num = m
            factors = {}
            while num > 1:
                p = min_prime[num]
                cnt = 0
                while num % p == 0:
                    cnt += 1
                    num //= p
                factors[p] = cnt
            factor_list[m] = factors.copy() if factors else {}
        
        # 步骤 2：预计算 fact 和 inv_fact，最多 N=2e5.
        N_fact = 2 * 10**5
        fact = [1] * (N_fact + 1)
        for i in range(1, N_fact + 1):
            fact[i] = (fact[i-1] * i) % MOD
        
        inv_fact = [1]*(N_fact + 1)
        inv_fact[N_fact] = pow(fact[N_fact], MOD -2, MOD)
        for i in range(N_fact -1, -1, -1):
            inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD
        
        # 步骤 3：计算 fm 数组.
        fm = [0]*(max_num + 1)  # 从 0 到 maxValue 的索引.
        
        for m in range(1, max_num + 1):
            if m == 1:
                factors_dict = {}
            else:
                factors_dict = factor_list[m]
            
            product = 1
            for p in factors_dict:
                a_i = factors_dict[p]
                n_val = a_i + t - 1
                k_val = t - 1
                
                # 选择 k 和 (n_val -k) 之间的较小值，以减少计算量.
                if k_val > (n_val - k_val):
                    k_val = n_val - k_val
                
                # 计算 C(n_val, k_val)
                c_n_k = fact[n_val] * inv_fact[k_val] % MOD
                c_n_k = c_n_k * inv_fact[n_val - k_val] % MOD
                product = (product * c_n_k) % MOD
            
            fm[m] = product
        
        # 计算前缀数组.
        prefix = [0]*(max_num + 1)
        for i in range(1, max_num+1):
            prefix[i] = (prefix[i-1] + fm[i]) % MOD
        
        res = 0
        for a_val in range(1, maxValue + 1):
            m_max = maxValue // a_val
            res += prefix[m_max]
            res %= MOD
        
        return res