HardRating 2500

1735. Count Ways to Make Array With Product

arraymathdynamic-programmingcombinatoricsnumber-theory

解題說明

Count Ways to Make Array With Product

題目描述：給定多個查詢 queries[i] = [n, k]，對每個查詢求有多少個長度為 n 的正整數陣列，使得所有元素的乘積恰好為 k。答案取模 10^9 + 7。

解題思路：將 k 質因數分解為 k = p1^e1 × p2^e2 × ...。對於每個質因子 pi 的指數 ei，問題等價於將 ei 個相同球放入 n 個不同盒子（隔板法），方案數為 C(ei + n - 1, n - 1)。最終答案為各質因子的方案數之積。預先計算階乘和逆階乘以快速求組合數。

C++ 解法

複雜度分析

時間複雜度：O(MAXN + Q × sqrt(k)) — 預處理階乘 O(MAXN)，每個查詢質因數分解 O(sqrt(k))，組合數查詢 O(1)。

空間複雜度：O(MAXN) — 階乘和逆階乘陣列。

虛擬碼

1. Precompute factorial and inverse factorial arrays up to MAXN
2. For each query (n, k):
   a. Factorize k into prime factors with exponents
   b. For each prime factor with exponent e:
      - Multiply result by C(e + n - 1, n - 1)
   c. Append result to answer
3. Return answer array

其他解法

DP 分配法：用 DP 直接計算 dp[i][j] 表示前 i 個位置乘積為 j 的方案數。時間 O(n × k × divisors(k))，適合 k 小的情況，但不適合 k 達到 10^4。

生成函數：將問題建模為多項式係數，用生成函數理論推導封閉公式。數學上更優雅但實作難度高。

延伸思考

若要求陣列元素必須是不同的正整數，問題如何變化？
若 k 很大（例如 10^12），質因數分解的效率如何保證？
若陣列元素有上界限制（每個元素不超過 M），如何調整？

Count Ways to Make Array With Product — CaffeCode