好子集的数目之解决方案

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

解决方案：状态压缩动态规划。

思路

注意到题目规定数组 nums 中的元素不超过 30 ，因此我们可以将 [1,30] 中的整数分成如下三类：

1：对于任意一个好子集而言，我们添加任意数目的 1 ，得到的新子集仍然是好子集；
2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30 ：这些数均不包含平方因子，因此每个数在好子集中至多出现一次；
4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28：这些数包含平方因子，因此一定不能在好子集中出现。
我们可以通过硬编码的方式把 [1, 30] 中的整数按照上述分类，也可以先预处理出所有 [1, 30] 中质数 2, 3, 5, 7, 11, 13, 17, 19, 23, 29，再通过试除的方式动态分类。

分类完成后，我们就可以考虑动态规划了。由于每个质因数只能出现一次，并且 [1, 30] 中一共有 10 个质数，因此我们可以用一个长度为 10 的二进制数 mask 表示这些质因数的使用情况，其中 mask 的第 i 位为 1 当且仅当第 i 个质数已经被使用过。

这样一来，我们定义 f[i][mask] 表示当我们只选择 [2,i] 范围内的数，并且选择的数的质因数使用情况为 mask 时的方案数。如果 i 本身包含平方因子，那么我们无法选择 i ，相当于在 [2,i − 1] 范围内选择，状态转移方程为：

f[i][mask] = f[i − 1][mask]

如果 i 本身不包含平方因子，记其包含的质因子的二进制表示为 subset（同样可以通过试除的方法得到），那么状态转移方程为：

f[i][mask] = f[i − 1][mask] + f[i − 1][mask\subset] × freq[i]

其中：

freq[i] 表示数组 nums 中 i 出现的次数；
mask\subset 表示从二进制表示 mask 中去除所有在 subset 中出现的 1，可以使用按位异或运算实现。这里需要保证 subset 是 mask 的子集，可以使用按位与运算来判断。
动态规划的边界条件为：

f[1][0] = 2freq[1]

即每一个在数组 nums 中出现的 1 都可以选或不选。最终的答案即为所有 f[30][..] 中除了 f[30][0] 以外的项的总和。

细节

注意到 f[i][mask] 只会从 f[i − 1][..] 转移而来，并且 f[i − 1][..] 中的下标总是小于 mask ，因此我们可以使用类似 0 - 1 背包的空间优化方法，在遍历 mask 时从 210 − 1 到 1 逆序遍历，这样就只需要使用一个长度为 210 的一维数组做状态转移了。

代码

C++

class Solution:def numberOfGoodSubsets(self, nums: List[int]) -> int:primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]mod = 10**9 + 7freq = Counter(nums)f = [0] * (1 << len(primes))f[0] = pow(2, freq[1], mod)for i, occ in freq.items():if i == 1:continue# 检查 i 的每个质因数是否均不超过 1 个subset, x = 0, icheck = Truefor j, prime in enumerate(primes):if x % (prime * prime) == 0:check = Falsebreakif x % prime == 0:subset |= (1 << j)if not check:continue# 动态规划for mask in range((1 << len(primes)) - 1, 0, -1):if (mask & subset) == subset:f[mask] = (f[mask] + f[mask ^ subset] * occ) % modans = sum(f[1:]) % modreturn ans
好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！