Count ways to make array with product

Array Math Dynamic Programming Combinatorics Number Theory

54.4% acceptance

Feb 25, 2026

319

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn ways_to_fill_array(queries: Vec<Vec<i32>>) -> Vec<i32> {
    const MOD: i64 = 1_000_000_007;
    const MAXN: usize = 20001;

    // Precompute factorials and inverse factorials
    let mut fact = vec![1i64; MAXN];
    for i in 1..MAXN { fact[i] = fact[i - 1] * i as i64 % MOD; }
    let mut inv_fact = vec![1i64; MAXN];
    inv_fact[MAXN - 1] = Self::pow_mod(fact[MAXN - 1], MOD - 2, MOD);
    for i in (0..MAXN - 1).rev() { inv_fact[i] = inv_fact[i + 1] * (i + 1) as i64 % MOD; }

    let comb = |n: i64, r: i64| -> i64 {
      if r < 0 || r > n { return 0; }
      fact[n as usize] * inv_fact[r as usize] % MOD * inv_fact[(n - r) as usize] % MOD
    };

    queries.iter().map(|q| {
      let (n, mut k) = (q[0] as i64, q[1] as i64);
      let mut ans = 1i64;
      let mut p = 2i64;
      while p * p <= k {
        if k % p == 0 {
          let mut e = 0i64;
          while k % p == 0 { k /= p; e += 1; }
          // Stars and bars: C(n + e - 1, e)
          ans = ans * comb(n + e - 1, e) % MOD;
        }
        p += 1;
      }
      if k > 1 { ans = ans * comb(n, 1) % MOD; } // one prime factor with e=1: C(n,1)=n
      ans as i32
    }).collect()
  }

  fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
    let mut result = 1i64;
    base %= modulus;
    while exp > 0 {
      if exp & 1 == 1 { result = result * base % modulus; }
      exp >>= 1;
      base = base * base % modulus;
    }
    result
  }
}