Count Ways to Make Array With Product LeetCode solution in C++

1
#define MOD 1000000007
2

3
// calculating combinatorics
4
long long comb(int n, int m) {
5
  static long long c[20001][10001] = {0};
6
  if (c[n][m] != 0) return c[n][m];
7
  long long res;
8
  if (m == 0 || m == n)
9
    res = 1;
10
  else
11
    res = (comb(n - 1, m) + comb(n - 1, m - 1)) % MOD;
12
  c[n][m] = res;
13
  return res;
14
}
15

16
class Solution {
17
 public:
18
  vector<int> waysToFillArray(vector<vector<int>> &queries) {
19
    vector<int> factors;
20
    vector<int> res;
21
    for (int i = 0; i < queries.size(); i++) {
22
      // counting numbers of distinct prime factors
23
      // note that numbers within 10000 have at most 1 prime factor over 100
24
      // if we loop to queries[i][1] here we will get a TLE since one loop grows
25
      // from 100 to 10000 here
26
      factors.clear();
27
      for (int j = 2; j <= 97; j++) {
28
        if (queries[i][1] % j == 0) {
29
          int count = 0;
30
          while (queries[i][1] % j == 0) {
31
            count++;
32
            queries[i][1] /= j;
33
          }
34
          factors.push_back(count);
35
        }
36
      }
37
      if (queries[i][1] != 1) factors.push_back(1);
38

39
      // calculate ways
40
      int tmp = 1;
41
      for (int f : factors) {
42
        tmp = (tmp * comb(f + queries[i][0] - 1, queries[i][0] - 1)) % MOD;
43
      }
44
      res.push_back(tmp);
45
    }
46
    return res;
47
  }
48
};