HardRating 2465
1994. The Number of Good Subsets
arrayhash-tablemathdynamic-programmingbit-manipulationcountingnumber-theorybitmask
解題說明
The Number of Good Subsets
題目描述：給定整數陣列 nums（元素範圍 1-30），找出「好子集」的數量。好子集的乘積可以表示為一個或多個不同質數的乘積（即乘積是無平方因子數 squarefree）。
解題思路：範圍 1-30 中的質數為 {2,3,5,7,11,13,17,19,23,29}，共 10 個。含平方因子的數（4,8,9,12,16,18,20,24,25,27,28）直接排除。對剩餘合法數字用 bitmask DP：dp[mask] 表示選取的數字所用質因子集合為 mask 的方案數。對每個合法數字 v，枚舉所有包含 v 的質因子集合的 mask，進行轉移。數字 1 不影響乘積，最終答案乘以 2^(count_of_1)（每個 1 可選可不選），再減 1（排除空集）。
C++ 解法
複雜度分析
時間複雜度：O(30 × 2^10) = O(30720) — 枚舉 30 個值，每個值遍歷 2^10 個 mask 狀態。
空間複雜度：O(2^10) — DP 陣列大小為 1024。
虛擬碼
1. Count frequency of each value 1..30
2. For each value 2..30, compute its prime bitmask (skip if has square factor)
3. dp[0] = 1
4. For each valid value v with count > 0:
a. For each mask s (high to low) not overlapping with v's mask:
- dp[s | v_mask] += dp[s] * cnt[v]
5. Sum dp[s] for all non-zero s
6. Multiply by 2^cnt[1]
7. Return result mod 10^9+7其他解法
回溯枚舉：枚舉 1-30 中所有合法數字的組合，檢查質因子不重疊。時間指數級但值域小（最多 ~15 個合法數字），加上剪枝可行。
容斥原理：利用莫比烏斯函數和容斥原理計算無平方因子乘積的子集數。數學上更優雅但實作門檻高。
延伸思考
- 若元素範圍擴大到 1-100，質數數量增加，bitmask 方法是否仍可行？
- 若要求乘積恰好等於某個特定值 k，如何修改？
- 若允許每個質數出現最多兩次（而非恰好一次），問題如何變化？