Question

1735. Count Ways to Make Array With Product

中文文档

Description

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:

• 1 <= queries.length <= 104
• 1 <= ni, ki <= 104

Solutions

Solution 1: Prime Factorization + Combinatorial Mathematics

We can perform prime factorization on $k$, i.e., $k = p_1^{x_1} \times p_2^{x_2} \times \cdots \times p_m^{x_m}$, where $p_i$ is a prime number, and $x_i$ is the exponent of $p_i$. The problem is equivalent to: placing $x_1$ $p_1$s, $x_2$ $p_2$s, $\cdots$, $x_m$ $p_m$s into $n$ positions respectively, where a single position can be empty. The question is how many schemes are there.

According to combinatorial mathematics, there are two cases when we put $x$ balls into $n$ boxes:

If the box cannot be empty, the number of schemes is $C_{x-1}^{n-1}$. This is using the partition method, i.e., there are a total of $x$ balls, and we insert $n-1$ partitions at $x-1$ positions, thereby dividing the $x$ balls into $n$ groups.

If the box can be empty, we can add $n$ virtual balls, and then use the partition method, i.e., there are a total of $x+n$ balls, and we insert $n-1$ partitions at $x+n-1$ positions, thereby dividing the actual $x$ balls into $n$ groups and allowing the box to be empty. Therefore, the number of schemes is $C_{x+n-1}^{n-1}$.

Therefore, for each query $queries[i]$, we can first perform prime factorization on $k$ to get the exponents $x_1, x_2, \cdots, x_m$, then calculate $C_{x_1+n-1}^{n-1}, C_{x_2+n-1}^{n-1}, \cdots, C_{x_m+n-1}^{n-1}$, and finally multiply all the scheme numbers.

So, the problem is transformed into how to quickly calculate $C_m^n$. According to the formula $C_m^n = \frac{m!}{n!(m-n)!}$, we can pre-process $m!$, and then use the inverse element to quickly calculate $C_m^n$.

The time complexity is $O(K \times \log \log K + N + m \times \log K)$, and the space complexity is $O(N)$.

N = 10020
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
p = defaultdict(list)
for i in range(1, N):
  f[i] = f[i - 1] * i % MOD
  g[i] = pow(f[i], MOD - 2, MOD)
  x = i
  j = 2
  while j <= x // j:
    if x % j == 0:
      cnt = 0
      while x % j == 0:
        cnt += 1
        x //= j
      p[i].append(cnt)
    j += 1
  if x > 1:
    p[i].append(1)


def comb(n, k):
  return f[n] * g[k] * g[n - k] % MOD


class Solution:
  def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
    ans = []
    for n, k in queries:
      t = 1
      for x in p[k]:
        t = t * comb(x + n - 1, n - 1) % MOD
      ans.append(t)
    return ans

class Solution {
  private static final int N = 10020;
  private static final int MOD = (int) 1e9 + 7;
  private static final long[] F = new long[N];
  private static final long[] G = new long[N];
  private static final List<Integer>[] P = new List[N];

  static {
    F[0] = 1;
    G[0] = 1;
    Arrays.setAll(P, k -> new ArrayList<>());
    for (int i = 1; i < N; ++i) {
      F[i] = F[i - 1] * i % MOD;
      G[i] = qmi(F[i], MOD - 2, MOD);
      int x = i;
      for (int j = 2; j <= x / j; ++j) {
        if (x % j == 0) {
          int cnt = 0;
          while (x % j == 0) {
            ++cnt;
            x /= j;
          }
          P[i].add(cnt);
        }
      }
      if (x > 1) {
        P[i].add(1);
      }
    }
  }

  public static long qmi(long a, long k, long p) {
    long res = 1;
    while (k != 0) {
      if ((k & 1) == 1) {
        res = res * a % p;
      }
      k >>= 1;
      a = a * a % p;
    }
    return res;
  }

  public static long comb(int n, int k) {
    return (F[n] * G[k] % MOD) * G[n - k] % MOD;
  }

  public int[] waysToFillArray(int[][] queries) {
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      int n = queries[i][0], k = queries[i][1];
      long t = 1;
      for (int x : P[k]) {
        t = t * comb(x + n - 1, n - 1) % MOD;
      }
      ans[i] = (int) t;
    }
    return ans;
  }
}

int N = 10020;
int MOD = 1e9 + 7;
long f[10020];
long g[10020];
vector<int> p[10020];

long qmi(long a, long k, long p) {
  long res = 1;
  while (k != 0) {
    if ((k & 1) == 1) {
      res = res * a % p;
    }
    k >>= 1;
    a = a * a % p;
  }
  return res;
}

int init = []() {
  f[0] = 1;
  g[0] = 1;
  for (int i = 1; i < N; ++i) {
    f[i] = f[i - 1] * i % MOD;
    g[i] = qmi(f[i], MOD - 2, MOD);
    int x = i;
    for (int j = 2; j <= x / j; ++j) {
      if (x % j == 0) {
        int cnt = 0;
        while (x % j == 0) {
          ++cnt;
          x /= j;
        }
        p[i].push_back(cnt);
      }
    }
    if (x > 1) {
      p[i].push_back(1);
    }
  }
  return 0;
}();

int comb(int n, int k) {
  return (f[n] * g[k] % MOD) * g[n - k] % MOD;
}

class Solution {
public:
  vector<int> waysToFillArray(vector<vector<int>>& queries) {
    vector<int> ans;
    for (auto& q : queries) {
      int n = q[0], k = q[1];
      long long t = 1;
      for (int x : p[k]) {
        t = t * comb(x + n - 1, n - 1) % MOD;
      }
      ans.push_back(t);
    }
    return ans;
  }
};

const n = 1e4 + 20
const mod = 1e9 + 7

var f = make([]int, n)
var g = make([]int, n)
var p = make([][]int, n)

func qmi(a, k, p int) int {
  res := 1
  for k != 0 {
    if k&1 == 1 {
      res = res * a % p
    }
    k >>= 1
    a = a * a % p
  }
  return res
}

func init() {
  f[0], g[0] = 1, 1
  for i := 1; i < n; i++ {
    f[i] = f[i-1] * i % mod
    g[i] = qmi(f[i], mod-2, mod)
    x := i
    for j := 2; j <= x/j; j++ {
      if x%j == 0 {
        cnt := 0
        for x%j == 0 {
          cnt++
          x /= j
        }
        p[i] = append(p[i], cnt)
      }
    }
    if x > 1 {
      p[i] = append(p[i], 1)
    }
  }
}

func comb(n, k int) int {
  return (f[n] * g[k] % mod) * g[n-k] % mod
}

func waysToFillArray(queries [][]int) (ans []int) {
  for _, q := range queries {
    n, k := q[0], q[1]
    t := 1
    for _, x := range p[k] {
      t = t * comb(x+n-1, n-1) % mod
    }
    ans = append(ans, t)
  }
  return
}