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.

 

Example 1:

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 109 + 7 = 50734910.
Example 2:

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

Constraints:


Solution:

6 factorized as {2, 3} which is {2}{3}
First we distribute {2} into array of size 2(1 star 1 bar), r1 = 1, n = 2:


2|
 |2

Then we distribute {3} into array of size 2(1 star 1 bar), r2 = 1, n = 2:


3|
 |3

combine:


23|
 2|3 
 3|2
  |23

We can see there is no duplicates and the result is comb(r1 + n - 1, r1) * comb(r2 + n - 1, r2) = 2*2 = 4
The empty slot will be filled by 1, and this calculation could be generalized to other situations like {2,2,2}{3,3}{5}

note that (n + r - 1, n) == (n + r - 1, r)

class Solution {
    int mod = (int) 1e9 + 7;
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
                53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    
    public int[] waysToFillArray(int[][] queries) {
        // 10014 = max(n + r - 1)
        // max(r) = 14 because for the smallest prime, 2^14 > 10000
        int[][] comb = new int[10014][14];
        comb[0][0] = 1;
        for (int n = 1; n < 10014; n ++) {
            for (int c = 0; c < 14; c ++) {
                if (c == 0) comb[n][c] = 1;
                else {
                    comb[n][c] = (comb[n - 1][c - 1] + comb[n - 1][c]) % mod;
                }
            }
        }
        int[] res = new int[queries.length];
        Arrays.fill(res, 1);
        for (int i = 0; i < queries.length; i ++) {
            int[] query = queries[i];
            int n = query[0], k = query[1];
            for (int prime : primes) {
                if (prime > k) break;
                int r = 0;
                while (k % prime == 0) {
                    k = k / prime;
                    r ++;
                }
                // System.out.println(prime + ", " + r);
                // System.out.println(comb[n + r - 1][r]);

                res[i] = (int) ((res[i] * (long) comb[n + r - 1][r]) % mod);
            }
            if (k != 1) {
                res[i] = (int) ((res[i] * (long) n) % mod);
            }
        }
        return res;
    }
}