Count Ways to Make Array With Product

Problem

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [ni, ki], find the number of different ways you can place positive integers into an array of size ni such that the product of the integers is ki. As the number of ways may be too large, the answer to the ith query is the number of ways modulo 10^9 + 7.

Return an integer arrayanswer whereanswer.length == queries.length , andanswer[i]is the answer to theith query.

Examples

Example 1

1
2
3
4
5
6


Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation:  Each query is independent.
[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].
[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].
[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 10^9 + 7 = 50734910.

Example 2

1
2


Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]

Constraints

1 <= queries.length <= 10^4
1 <= ni, ki <= 10^4

Solution

Method 1 – Prime Factorization + Stars and Bars (Combinatorics)

Intuition

The key idea is to break down the product ki into its prime factors. For each prime factor, we need to distribute its total exponent among ni slots (array elements). This is a classic combinatorics problem (stars and bars): the number of ways to distribute e identical items into n bins is C(n+e-1, e). The answer for each query is the product of such combinations for all prime factors of ki.

Approach

Precompute factorials and inverse factorials up to the maximum possible value (2 * 10^4) for efficient nCr calculation modulo 1e9+7.
For each query [n, k]:
- Factorize k into its prime factors and their exponents.
- For each prime factor with exponent e, compute C(n+e-1, e).
- Multiply all such combinations for all prime factors.
Return the result for each query.

Code

 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


class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    vector<long long> fact, inv;
    long long power(long long a, long long b) {
        long long res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    void build(int N) {
        fact.resize(N+1, 1);
        inv.resize(N+1, 1);
        for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
        inv[N] = power(fact[N], MOD-2);
        for (int i = N-1; i >= 0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
    }
    long long comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
    }
    vector<int> waysToFillArray(vector<vector<int>>& queries) {
        build(20000);
        vector<int> ans;
        for (auto& q : queries) {
            int n = q[0], k = q[1];
            long long res = 1;
            for (int d = 2; d * d <= k; ++d) {
                int cnt = 0;
                while (k % d == 0) {
                    k /= d;
                    ++cnt;
                }
                if (cnt) res = res * comb(n+cnt-1, cnt) % MOD;
            }
            if (k > 1) res = res * comb(n, 1) % MOD;
            ans.push_back(res);
        }
        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
40
41
42
43
44
45
46
47
48
49
50
51


func waysToFillArray(queries [][]int) []int {
    const mod = 1e9 + 7
    N := 20000
    fact := make([]int, N+1)
    inv := make([]int, N+1)
    fact[0] = 1
    for i := 1; i <= N; i++ {
        fact[i] = fact[i-1] * i % mod
    }
    inv[N] = pow(fact[N], mod-2, mod)
    for i := N-1; i >= 0; i-- {
        inv[i] = inv[i+1] * (i+1) % mod
    }
    comb := func(n, k int) int {
        if k < 0 || k > n {
            return 0
        }
        return fact[n] * inv[k] % mod * inv[n-k] % mod
    }
    pow := func(a, b, m int) int {
        res := 1
        for b > 0 {
            if b&1 == 1 {
                res = res * a % m
            }
            a = a * a % m
            b >>= 1
        }
        return res
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        n, k := q[0], q[1]
        res := 1
        for d := 2; d*d <= k; d++ {
            cnt := 0
            for k%d == 0 {
                k /= d
                cnt++
            }
            if cnt > 0 {
                res = res * comb(n+cnt-1, cnt) % mod
            }
        }
        if k > 1 {
            res = res * comb(n, 1) % mod
        }
        ans[i] = res
    }
    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
40
41
42
43
44


class Solution {
    static final int MOD = 1_000_000_7;
    long[] fact, inv;
    long power(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    void build(int N) {
        fact = new long[N+1];
        inv = new long[N+1];
        fact[0] = 1;
        for (int i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
        inv[N] = power(fact[N], MOD-2);
        for (int i = N-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
    }
    long comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
    }
    public int[] waysToFillArray(int[][] queries) {
        build(20000);
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int n = queries[i][0], k = queries[i][1];
            long res = 1;
            for (int d = 2; d * d <= k; d++) {
                int cnt = 0;
                while (k % d == 0) {
                    k /= d;
                    cnt++;
                }
                if (cnt > 0) res = res * comb(n+cnt-1, cnt) % MOD;
            }
            if (k > 1) res = res * comb(n, 1) % MOD;
            ans[i] = (int) res;
        }
        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
40
41
42
43
44
45
46
47
48
49


class Solution {
    private val MOD = 1_000_000_7
    private lateinit var fact: LongArray
    private lateinit var inv: LongArray
    private fun power(a: Long, b: Long): Long {
        var a = a
        var b = b
        var res = 1L
        while (b > 0) {
            if (b and 1L == 1L) res = res * a % MOD
            a = a * a % MOD
            b = b shr 1
        }
        return res
    }
    private fun build(N: Int) {
        fact = LongArray(N+1) { 1L }
        inv = LongArray(N+1) { 1L }
        for (i in 1..N) fact[i] = fact[i-1] * i % MOD
        inv[N] = power(fact[N], MOD-2)
        for (i in N-1 downTo 0) inv[i] = inv[i+1] * (i+1) % MOD
    }
    private fun comb(n: Int, k: Int): Long {
        if (k < 0 || k > n) return 0L
        return fact[n] * inv[k] % MOD * inv[n-k] % MOD
    }
    fun waysToFillArray(queries: Array<IntArray>): IntArray {
        build(20000)
        val ans = IntArray(queries.size)
        for ((i, q) in queries.withIndex()) {
            var n = q[0]
            var k = q[1]
            var res = 1L
            var d = 2
            while (d * d <= k) {
                var cnt = 0
                while (k % d == 0) {
                    k /= d
                    cnt++
                }
                if (cnt > 0) res = res * comb(n+cnt-1, cnt) % MOD
                d++
            }
            if (k > 1) res = res * comb(n, 1) % MOD
            ans[i] = res.toInt()
        }
        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


class Solution:
    def waysToFillArray(self, queries: list[list[int]]) -> list[int]:
        MOD = 10**9 + 7
        N = 20000
        fact = [1] * (N+1)
        inv = [1] * (N+1)
        for i in range(1, N+1):
            fact[i] = fact[i-1] * i % MOD
        inv[N] = pow(fact[N], MOD-2, MOD)
        for i in range(N-1, -1, -1):
            inv[i] = inv[i+1] * (i+1) % MOD
        def comb(n: int, k: int) -> int:
            if k < 0 or k > n:
                return 0
            return fact[n] * inv[k] % MOD * inv[n-k] % MOD
        ans = []
        for n, k in queries:
            res = 1
            d = 2
            while d * d <= k:
                cnt = 0
                while k % d == 0:
                    k //= d
                    cnt += 1
                if cnt:
                    res = res * comb(n+cnt-1, cnt) % MOD
                d += 1
            if k > 1:
                res = res * comb(n, 1) % MOD
            ans.append(res)
        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
40
41
42
43
44
45
46
47
48
49
50
51
52


impl Solution {
    pub fn ways_to_fill_array(queries: Vec<Vec<i32>>) -> Vec<i32> {
        const MOD: i64 = 1_000_000_007;
        let n = 20000;
        let mut fact = vec![1i64; n+1];
        let mut inv = vec![1i64; n+1];
        for i in 1..=n {
            fact[i] = fact[i-1] * i as i64 % MOD;
        }
        inv[n] = pow(fact[n], MOD-2, MOD);
        for i in (0..n).rev() {
            inv[i] = inv[i+1] * (i as i64 + 1) % MOD;
        }
        fn pow(mut a: i64, mut b: i64, m: i64) -> i64 {
            let mut res = 1;
            while b > 0 {
                if b & 1 == 1 {
                    res = res * a % m;
                }
                a = a * a % m;
                b >>= 1;
            }
            res
        }
        fn comb(n: usize, k: usize, fact: &Vec<i64>, inv: &Vec<i64>) -> i64 {
            if k > n { return 0; }
            fact[n] * inv[k] % MOD * inv[n-k] % MOD
        }
        let mut ans = vec![];
        for q in queries {
            let (mut n, mut k) = (q[0] as usize, q[1] as i64);
            let mut res = 1i64;
            let mut d = 2i64;
            while d * d <= k {
                let mut cnt = 0;
                while k % d == 0 {
                    k /= d;
                    cnt += 1;
                }
                if cnt > 0 {
                    res = res * comb(n+cnt-1, cnt, &fact, &inv) % MOD;
                }
                d += 1;
            }
            if k > 1 {
                res = res * comb(n, 1, &fact, &inv) % MOD;
            }
            ans.push(res as i32);
        }
        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 {
    waysToFillArray(queries: number[][]): number[] {
        const MOD = 1e9 + 7;
        const N = 20000;
        const fact: number[] = Array(N+1).fill(1);
        const inv: number[] = Array(N+1).fill(1);
        for (let i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
        inv[N] = pow(fact[N], MOD-2, MOD);
        for (let i = N-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
        function pow(a: number, b: number, m: number): number {
            let res = 1;
            while (b > 0) {
                if (b & 1) res = res * a % m;
                a = a * a % m;
                b >>= 1;
            }
            return res;
        }
        function comb(n: number, k: number): number {
            if (k < 0 || k > n) return 0;
            return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
        }
        const ans: number[] = [];
        for (const [n, k0] of queries) {
            let k = k0, res = 1;
            for (let d = 2; d * d <= k; d++) {
                let cnt = 0;
                while (k % d === 0) {
                    k = Math.floor(k / d);
                    cnt++;
                }
                if (cnt) res = res * comb(n+cnt-1, cnt) % MOD;
            }
            if (k > 1) res = res * comb(n, 1) % MOD;
            ans.push(res);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(Q * sqrt(K) + N), where Q is the number of queries, K is the max value of ki, and N is the max value for factorial precomputation.
🧺 Space complexity: O(N), for factorial and inverse factorial arrays.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Prime Factorization + Stars and Bars (Combinatorics)#

Intuition#

Approach#

Code#

Complexity#