Count Ways To Make Array With Product

• The idea behind this approach is that DP[N][P] will hold our result for any query.
• So we will build a solution step by step in a bottom-up manner.
• We will create a DP table in which each DP[i][j] state will represent the ways to make an array of size i with a product of j.
• The recurrence relation that we will use will be:

DP[i][j] = DP[i][j] + sum of (DP[i-1][j / divisors(j)]).

• The number of elements reduces by one because we have added the divisor j in our current array so to add another divisor i.e j / divisor we have reduced the size of the array by 1.

Algorithm:

• Create an array ans to store the answer to each query.
• Now iterate over all queries and for each query perform the following steps:
  • Create a DP table of size (N+1) * (P+1) all initialized with 0.
  • Now fill the first row of the DP table i.e DP[1][j] starting from j=1 to j = P with 1 because to fill an array of size 1 there could be only one way.
  • Similarly, fill the first column of the DP table i.e DP[i][1] starting from i = 1 to i = N with 1 because to build an array with product 1 there could be only one way.
  • Now for each i from 2 to N take the value of j from 2 to P and for each value of j perform the following steps:
    • For each divisor of j update DP[i][j] as DP[i][j] = DP[i][j]  + DP[i-1][j/divisor(j)].
    • Then update DP[i][j] as DP[i][j] % 1000000007.
  • Now finally add DP[N][P] in our ans.
• Finally, return the array ans.

• Since we want to construct an array of size N such that the product of its elements is equal to P. So we know that every number can be represented in the form of its prime factors, so we will prime factorize P and store the frequency of each prime factor.
• Now the second part of the problem is that we have to arrange these prime factors in N slots. So the problem is reduced to a combinatorics problem.
• Since we have to arrange prime factors over N slots so we will consider the frequency of each prime factor. Now in some cases, prime factors can repeat also so we have to consider the permutations of each prime factor independently.
• So now the problem is similar to the classical problem of the stars and bars method where we can assume that we have K identical prime factors and we have to place them in N slots. Then the number of ways to perform it will be (N+K-1)C(K) where C denotes the Binomial Coefficient.
• The calculation method of the final answer will be to decompose prime factor P = X1^P1 * X2^P2 * X3^P3 * …. The total number of arrays generated  = permute P1 (same prime factor X1) into N slots * permute P2 (same prime factor X2) into N slots * permute P3 (same prime factor X3) into N slots … and so on.
• So for the count of each distinct prime factor say (P1, P2, P3..) the total number of ways will be :

((P1 + N - 1)C(P1)) * ((P2 + N - 1)C(P2)) * ((P3 + N - 1)C(P3))...

,where C denotes the Binomial Coefficient. 

Algorithm:

• We will first create a table of binomial coefficients combination to precompute all values of binomial coefficients(N choose R) till N = 10^4 and R = 14. We are choosing R = 14 because at max 14 spaces will be filled by any particular prime factor as 2^14 <= 10^4. Then we can use it later to directly take results from it.
• Precompute the smallest prime factor for every number till 10^4 using a sieve.
• Create an array result to store the answer to each query.
• Iterate over all queries and for each query perform the following steps:
  • Create a variable ans initialized it to 1 to store the answer to each query.
  • First, find the count of each prime factor of P using the smallest prime factor precomputed using a sieve and store it in a variable count.
  • And then for each count of prime factor update the ans as ans * combination[count + N - 1][count] % (1000000007).
  • Then insert the ans into our Result array.
• Finally, return the result as our required answer.