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 modulo10^9 + 7.
Return an integer arrayanswerwhereanswer.length == queries.length, andanswer[i]is the answer to theithquery.
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 is1 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.
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.
classSolution {
public:staticconstexprint MOD =1e9+7;
vector<longlong> fact, inv;
longlongpower(longlong a, longlong b) {
longlong res =1;
while (b) {
if (b &1) res = res * a % MOD;
a = a * a % MOD;
b >>=1;
}
return res;
}
voidbuild(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;
}
longlongcomb(int n, int k) {
if (k <0|| k > n) return0;
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];
longlong 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;
}
};
classSolution {
staticfinalint MOD = 1_000_000_7;
long[] fact, inv;
longpower(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;
}
voidbuild(int N) {
fact =newlong[N+1];
inv =newlong[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;
}
longcomb(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]* inv[k]% MOD * inv[n-k]% MOD;
}
publicint[]waysToFillArray(int[][] queries) {
build(20000);
int[] ans =newint[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;
}
}
classSolution {
privateval MOD = 1_000_000_7
privatelateinitvar fact: LongArray
privatelateinitvar inv: LongArray
privatefunpower(a: Long, b: Long): Long {
var a = a
var b = b
var res = 1Lwhile (b > 0) {
if (b and 1L==1L) res = res * a % MOD
a = a * a % MOD
b = b shr 1 }
return res
}
privatefunbuild(N: Int) {
fact = LongArray(N+1) { 1L }
inv = LongArray(N+1) { 1L }
for (i in1..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
}
privatefuncomb(n: Int, k: Int): Long {
if (k < 0|| k > n) return0Lreturn fact[n] * inv[k] % MOD * inv[n-k] % MOD
}
funwaysToFillArray(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 = 1Lvar d = 2while (d * d <= k) {
var cnt = 0while (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
}
}
classSolution:
defwaysToFillArray(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
defcomb(n: int, k: int) -> int:
if k <0or k > n:
return0return fact[n] * inv[k] % MOD * inv[n-k] % MOD
ans = []
for n, k in queries:
res =1 d =2while d * d <= k:
cnt =0while k % d ==0:
k //= d
cnt +=1if cnt:
res = res * comb(n+cnt-1, cnt) % MOD
d +=1if k >1:
res = res * comb(n, 1) % MOD
ans.append(res)
return ans
impl Solution {
pubfnways_to_fill_array(queries: Vec<Vec<i32>>) -> Vec<i32> {
constMOD: i64=1_000_000_007;
let n =20000;
letmut fact =vec![1i64; n+1];
letmut inv =vec![1i64; n+1];
for i in1..=n {
fact[i] = fact[i-1] * i asi64%MOD;
}
inv[n] = pow(fact[n], MOD-2, MOD);
for i in (0..n).rev() {
inv[i] = inv[i+1] * (i asi64+1) %MOD;
}
fnpow(mut a: i64, mut b: i64, m: i64) -> i64 {
letmut res =1;
while b >0 {
if b &1==1 {
res = res * a % m;
}
a = a * a % m;
b >>=1;
}
res
}
fncomb(n: usize, k: usize, fact: &Vec<i64>, inv: &Vec<i64>) -> i64 {
if k > n { return0; }
fact[n] * inv[k] %MOD* inv[n-k] %MOD }
letmut ans =vec![];
for q in queries {
let (mut n, mut k) = (q[0] asusize, q[1] asi64);
letmut res =1i64;
letmut d =2i64;
while d * d <= k {
letmut 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 asi32);
}
ans
}
}
⏰ 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.