How do I start solving Count Ways to Make Array With Product efficiently?

Begin by prime factorizing k for each query. Then, distribute prime exponents across n positions using combinatorial counting, applying modulo 10^9 + 7.

Why is combinatorial DP used in this problem?

Combinatorial DP counts the ways to distribute prime exponents across positions, which is equivalent to placing identical items into distinct bins efficiently.

How should large numbers be handled in calculations?

Use modular arithmetic at every multiplication and combination step. Precompute factorials and modular inverses for fast combination evaluation.

Can this approach handle multiple queries efficiently?

Yes, by precomputing factorials and inverses, each query’s calculation reduces to processing prime distributions without recomputing combinatorial values.

Is state transition dynamic programming always necessary here?

Yes, DP effectively manages distributions of prime powers for each position, ensuring correct counts while handling constraints and modulo operations.

#1735

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

生成乘积数组的方案数

给你一个二维整数数组 queries ，其中 queries[i] = [n i , k i ] 。第 i 个查询 queries[i] 要求构造长度为 n i 、每个元素都是正整数的数组，且满足所有元素的乘积为 k i ，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 10 9 + …

数组数学动态规划组合数学数论

题目描述

给你一个二维整数数组 queries ，其中 queries[i] = [n_i, k_i] 。第 i 个查询 queries[i] 要求构造长度为 n_i 、每个元素都是正整数的数组，且满足所有元素的乘积为 k_i，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 10⁹ + 7 取余。

请你返回一个整数数组 answer，满足 answer.length == queries.length ，其中 answer[i]是第 i 个查询的结果。

示例 1：

输入：queries = [[2,6],[5,1],[73,660]]
输出：[4,1,50734910]
解释：每个查询之间彼此独立。
[2,6]：总共有 4 种方案得到长度为 2 且乘积为 6 的数组：[1,6]，[2,3]，[3,2]，[6,1]。
[5,1]：总共有 1 种方案得到长度为 5 且乘积为 1 的数组：[1,1,1,1,1]。
[73,660]：总共有 1050734917 种方案得到长度为 73 且乘积为 660 的数组。1050734917 对 10⁹ + 7 取余得到 50734910 。

示例 2 ：

输入：queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：[1,2,3,10,5]

提示：

1 <= queries.length <= 10⁴
1 <= n_i, k_i <= 10⁴

lightbulb

解题思路

方法一：质因数分解 + 组合数学

我们可以对 $k$ 进行质因数分解，即 $k = p_1^{x_1} \times p_2^{x_2} \times \cdots \times p_m^{x_m}$ ，其中 $p_i$ 为质数，而 $x_i$ 为 $p_i$ 的指数。那么题目实际上等价于：把 $x_1$ 个 $p_1$ , $x_2$ 个 $p_2$ , $\cdots$ , $x_m$ 个 $p_m$ 分别放到 $n$ 个位置上，单个位置可以为空，问有多少种方案。

根据组合数学的知识，我们把 $x$ 个球放入 $n$ 个盒子中，有两种情况：

如果盒子不能为空，那么方案数为 $C_{x-1}^{n-1}$ ，这里是利用隔板法，即一共 $x$ 个球，我们在其中 $x-1$ 个位置插入 $n-1$ 个隔板，从而将 $x$ 个球分成 $n$ 组。

如果盒子可以为空，那么我们可以再增加 $n$ 个虚拟球，然后再利用隔板法，即一共 $x+n$ 个球，我们在其中 $x+n-1$ 个位置插入 $n-1$ 个隔板，从而将实际的 $x$ 个球分成 $n$ 组，并且允许盒子为空，因此方案数为 $C_{x+n-1}^{n-1}$ 。

因此，对于每个查询 $queries[i]$ ，我们可以先对 $k$ 进行质因数分解，得到指数 $x_1, x_2, \cdots, x_m$ ，然后计算 $C_{x_1+n-1}^{n-1}, C_{x_2+n-1}^{n-1}, \cdots, C_{x_m+n-1}^{n-1}$ ，最后将所有的方案数相乘即可。

所以，问题转化为如何快速计算 $C_m^n$ ，根据公式 $C_m^n = \frac{m!}{n!(m-n)!}$ ，我们可以先预处理出 $m!$ ，然后利用逆元快速计算 $C_m^n$ 。

时间复杂度 $O(K \times \log \log K + N + m \times \log K)$ ，空间复杂度 $O(N)$ 。

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

N = 10020
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
p = defaultdict(list)
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)
    x = i
    j = 2
    while j <= x // j:
        if x % j == 0:
            cnt = 0
            while x % j == 0:
                cnt += 1
                x //= j
            p[i].append(cnt)
        j += 1
    if x > 1:
        p[i].append(1)


def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        ans = []
        for n, k in queries:
            t = 1
            for x in p[k]:
                t = t * comb(x + n - 1, n - 1) % MOD
            ans.append(t)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on prime factorization of k and the calculation of combinations for each prime exponent across n positions. Space complexity is mainly for factorial tables and storing intermediate results for each query.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to recognize prime factorization reduces multiplicative constraints to additive distributions.
question_mark
Look for correct handling of large numbers and modulo arithmetic in combinatorial calculations.
question_mark
Strong solutions efficiently precompute factorials to avoid recomputation for multiple queries.

warning

常见陷阱

外企场景

error
Failing to account for modulo arithmetic during combination calculations, leading to integer overflow.
error
Miscounting distributions of prime powers when exponents are large compared to n.
error
Not separating queries properly, causing mixing of results across independent queries.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting arrays with a sum constraint instead of a product using similar combinatorial DP techniques.
arrow_right_alt
Handling arrays with restricted value ranges, requiring adjusted prime distributions.
arrow_right_alt
Extending to multi-dimensional arrays where the product constraint applies along different axes.

help

常见问题

外企场景

继续练习

#1799 N 次操作后的最大分数和 #1643 第 K 条最小指令 #1569 将子数组重新排序得到同一个二叉搜索树的方案数