给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。
- 比方说，如果
nums = [1, 2, 3, 4]：[2, 3]，[1, 2, 3]和[1, 3]是 好 子集，乘积分别为6 = 2*3，6 = 2*3和3 = 3。[1, 4]和[4]不是 好 子集，因为乘积分别为4 = 2*2和4 = 2*2。
请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。
nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。
示例 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 <= nums.length <= 10^5\)
1 <= nums[i] <= 30- 只考虑只具有素数因子的数。
- 使用暴力找到所有可能的好子集，然后计算其在 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] = 2^{\textit{freq}[1]} \)
即每一个在数组 nums 中出现的 1 都可以选或不选。最终的答案即为所有 f[30][..] 中除了 f[30][0] 以外的项的总和。
细节
注意到 f[i][mask] 只会从 f[i−1][..] 转移而来，并且 f[i−1][..] 中的下标总是小于 mask，因此我们可以使用类似 0−1 背包的空间优化方法，在遍历 mask 时从 \(2^{10}−1\) 到 1 逆序遍历，这样就只需要使用一个长度为 \(2^{10}\) 的一维数组做状态转移了。
复杂度分析
时间复杂度：\(O(n + C \times 2^{\pi(C)})\)。其中 n 是数组 nums 的长度，C 是 nums 元素的最大值，在本题中 C=30，π(x) 表示 ≤x 的质数的个数。
我们一共需要考虑 O(C) 个数，每个数需要 \(O(2^{\pi(C)})\) 的时间计算动态规划；
除此之外，在初始时我们还需要遍历一遍所有的数，时间复杂度为 O(n)。
空间复杂度：\(O(2^{\pi(C)})\)，即为动态规划需要使用的空间。
class Solution {
private:
static constexpr array<int, 10> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
static constexpr int num_max = 30;
static constexpr int mod = 1000000007;
static constexpr int mask_max = 1 << primes.size();
public:
static int numberOfGoodSubsets(vector<int> &nums) {
vector<int> freq(num_max + 1);
for(const int num: nums) {
freq[num]++;
}
vector<int> f(mask_max);
f[0] = 1;
for(int i = 0; i < freq[1]; ++i) {
f[0] = f[0] * 2 % mod;
}
for(int i = 2; i <= num_max; ++i) {
if(freq[i] == 0) {
continue;
}
// 检查 i 的每个质因数是否均不超过 1 个
int subset = 0;
const int x = i;
bool check = true;
for(int j = 0; j < primes.size(); j++) {
const int prime = primes[j];
if(x % (prime * prime) == 0) {
check = false;
break;
}
if(x % prime == 0) {
subset |= 1 << j;
}
}
if(!check) {
continue;
}
// 动态规划
for(int mask = mask_max - 1; mask > 0; mask--) {
if((mask & subset) == subset) {
f[mask] = (f[mask] + static_cast<long long>(f[mask ^ subset]) * freq[i]) % mod;
}
}
}
int ans = 0;
for(int mask = 1; mask < mask_max; mask++) {
ans = (ans + f[mask]) % mod;
}
return ans;
}
};