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),如何調整?