[LeetCode] Count Ways to Make Array With Product

1735. Count Ways to Make Array With Product

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 109 + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the ith query.

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
class Solution {
vector<long long> sieve;
long long comb[101010][14] = {1};
long long mod = 1e9 + 7;
void prime() {
int p[1010] = {};
for(int i = 2; sieve.size() < 30; i++) {
if(p[i]) continue;
sieve.push_back(i);
for(int j = i * i; j < 1010; j += i)
p[j] = true;
}
}
void nCr() {
for(int n = 1; n < 101010; n++) {
for(int r = 0; r < 14; r++) {
comb[n][r] = !r ? 1 : (comb[n - 1][r - 1] + comb[n - 1][r]) % mod;
}
}
}
public:
vector<int> waysToFillArray(vector<vector<int>>& queries) {
prime();
nCr();
vector<int> res;
for(auto q : queries) {
int n = q[0], k = q[1];
long long ans = 1;
for(auto& s : sieve) {
int r = 0;
while(k % s == 0) {
r++;
k /= s;
}
ans = (ans * comb[n - 1 + r][r]) % mod;
}
if(k != 1) ans = (ans * n) % mod;
res.push_back(ans);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/22/PS/LeetCode/count-ways-to-make-array-with-product/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.