1994. 好子集的数目

• 标签：位运算、数组、数学、动态规划、状态压缩
• 难度：困难

题目链接

• 1994. 好子集的数目 - 力扣

题目大意

描述：给定一个整数数组 $nums$。

要求：返回 $nums$ 中不同的好子集的数目对 $10^9 + 7$ 取余的结果。

说明：

• 子集：通过删除 $nums$ 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

• 好子集：如果 $nums$ 的一个子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，那么我们称它为好子集。

  • 比如，如果 $nums = [1, 2, 3, 4]$：
    • $[2, 3]$，$[1, 2, 3]$ 和 $[1, 3]$ 是好子集，乘积分别为 $6 = 2 \times 3$ ，$6 = 2 \times 3$ 和 $3 = 3$。
    • $[1, 4]$ 和 $[4]$ 不是好子集，因为乘积分别为 $4 = 2 \times 2$ 和 $4 = 2 \times 2$。

• $1 \le nums.length \le 10^5$。

• $1 \le nums[i] \le 30$。

示例：

• 示例 1：

输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3，可以表示为质数 3 的乘积。
- [2]：乘积为 2，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3，可以表示为质数 3 的乘积。

• 示例 2：

输入：nums = [4,2,3,15]
输出：5
解释：好子集为：
- [2]：乘积为 2，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3，可以表示为质数 3 的乘积。
- [15]：乘积为 15，可以表示为互不相同质数 3 和 5 的乘积。

解题思路

思路 1：状态压缩 DP

根据题意可以看出：

1. 虽然 $nums$ 的长度是 $[1, 10^5]$，但是其值域范围只有 $[1, 30]$，则我们可以将 $[1, 30]$ 的数分为 $3$ 类：
   1. 质数：$[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$（共 $10$ 个数）。由于好子集的乘积拆解后的质因子只能包含这 $10$ 个，我们可以使用一个数组 $primes$ 记录下这 $10$ 个质数，将好子集的乘积拆解为质因子后，每个 $primes[i]$ 最多出现一次。
   2. 非质数：$[4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30]$。非质数肯定不会出现在好子集的乘积拆解后的质因子中。
   3. 特殊的数：$[1]$。对于一个好子集而言，无论向中间添加多少个 $1$，得到的新子集仍是好子集。
2. 分类完成后，由于 $[1, 30]$ 中只有 $10$ 个质数，因此我们可以使用一个长度为 $10$ 的二进制数 $state$ 来表示 $primes$ 中质因数的选择情况。其中，如果 $state$ 第 $i$ 位为 $1$，则说明第 $i$ 个质因数 $primes[i]$ 被使用过；如果 $state$ 第 $i$ 位为 $0$，则说明第 $i$ 个质因数 $primes[i]$ 没有被使用过。
3. 题目规定值相同，但是下标不同的子集视为不同子集，那么我们可先统计出 $nums$ 中每个数 $nums[i]$ 的出现次数，将其存入 $cnts$ 数组中，其中 $cnts[num]$ 表示 $num$ 出现的次数。这样在统计方案时，直接计算出 $num$ 的方案数，再乘以 $cnts[num]$ 即可。

接下来，我们就可以使用「动态规划」的方式来解决这道题目了。

1. 划分阶段

按照质因数的选择情况进行阶段划分。

2. 定义状态

定义状态 $dp[state]$ 表示为：当质因数选择的情况为 $state$ 时，好子集的数目。

3. 状态转移方程

对于 $nums$ 中的每个数 $num$，其对应出现次数为 $cnt$。我们可以通过试除法，将 $num$ 分解为不同的质因数，并使用「状态压缩」的方式，用一个二进制数 $cur\underline{\hspace{0.5em}}state$ 来表示当前数 $num$ 中使用了哪些质因数。然后枚举所有状态，找到与 $cur\underline{\hspace{0.5em}}state$ 不冲突的状态 $state$（也就是除了 $cur\underline{\hspace{0.5em}}state$ 中选择的质因数外，选择的其他质因数情况，比如 $cur\underline{\hspace{0.5em}}state$ 选择了 $2$ 和 $5$，则枚举不选择 $2$ 和 $5$ 的状态）。

此时，状态转移方程为：$dp[state | cur\underline{\hspace{0.5em}}state] = \sum (dp[state] \times cnt) \mod MOD , \quad state \text{ \& } cur\underline{\hspace{0.5em}}state == 0$

4. 初始条件

• 当 $state == 0$，所选质因数为空时，空集为好子集，则 $dp[0] = 1$。同时，对于一个好子集而言，无论向中间添加多少个 $1$，得到的新子集仍是好子集，所以对于空集来说，可以对应出 $2^{cnts[1]}$ 个方案，则最终 $dp[0] = 2^{cnts[1]}$。

5. 最终结果

根据我们之前定义的状态，$dp[state]$ 表示为：当质因数的选择的情况为 $state$ 时，好子集的数目。 所以最终结果为所有状态下的好子集数目累积和。所以我们可以枚举所有状态，并记录下所有好子集的数目和，就是最终结果。

思路 1：代码

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        MOD = 10 ** 9 + 7
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

        cnts = Counter(nums)
        dp = [0 for _ in range(1 << len(primes))]
        dp[0] = pow(2, cnts[1], MOD)            # 计算 1
		
        # num 分解质因数
        for num, cnt in cnts.items():           # 遍历 nums 中所有数及其频数
            if num == 1:                        # 跳过 1
                continue
                
            flag = True                         # 检查 num 的质因数是否都不超过 1
            cur_num = num                       
            cur_state = 0
            for i, prime in enumerate(primes):  # 对 num 进行试除
                cur_cnt = 0
                while cur_num % prime == 0:
                    cur_cnt += 1
                    cur_state |= 1 << i
                    cur_num //= prime
                if cur_cnt > 1:                 # 当前质因数超过 1，则 num 不能添加到子集中，跳过
                    flag = False
                    break
            if not flag:
                continue
            
            for state in range(1 << len(primes)):
                if state & cur_state == 0:      # 只有当前选择状态与前一状态不冲突时，才能进行动态转移
                    dp[state | cur_state] = (dp[state | cur_state] + dp[state] * cnt) % MOD
            
        ans = 0                                 # 统计所有非空集合的方案数
        for i in range(1, 1 << len(primes)):
            ans = (ans + dp[i]) % MOD

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n + m \times 2^p)$，其中 $n$ 为数组 $nums$ 的元素个数，$m$ 为 $nums$ 的最大值，$p$ 为 $[1, 30]$ 中的质数个数。
• 空间复杂度：$O(2^p)$。