leetcode-1994：好子集的数目
题目
题目链接
给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。
- 比方说，如果 nums = [1, 2, 3, 4] ：
[2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 23 ，6 = 23 和 3 = 3 。
[1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 22 和 4 = 22 。
请你返回 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 的乘积。
解题
方法一：状态压缩DP
class Solution {
public:
int MOD=1e9+7;
vector<int> p={2,3,5,7,11,13,17,19,23,29};
int numberOfGoodSubsets(vector<int>& nums) {
int n=nums.size();
vector<int> cnts(31,0); //题目规定数值相同，下标不同均视为不同方案，因此要统计每个数出现次数
for(int num:nums) cnts[num]++;
int mask=1<<10;
vector<long> f(mask);//利用位来记录每个质数使用状态，以此进行状态压缩
f[0]=1;
for(int i=2;i<=30;i++){
if(cnts[i]==0) continue;
int cur=0,x=i;
// 对 i 进行试除
bool ok=true;
for(int j=0;j<10;j++){
int t=p[j],c=0;
while(x%t==0){
cur|=(1<<j);
x/=t;
c++;
}
// 如果 i 能够被同一质数试除多次，说明 i 不能加到子集，跳过
if(c>1){
ok=false;
break;
}
}
if(!ok) continue;
// 枚举前一状态 prev
//（确保考虑一个新数值 i 时，依赖的子集 prev 存储的为尚未考虑 i 的方案数）
for(int prev=0;prev<mask;prev++){
// 只有当前选择数与前一状态不冲突，则能够进行转移，将方案数进行累加
if((prev&cur)!=0) continue;
f[prev|cur]=(f[prev|cur]+f[prev]*cnts[i])%MOD;
}
}
long res=0;
// 统计所有非空集的方案数（因为题目要求 子集数）
for(int i=1;i<mask;i++) res=(res+f[i])%MOD;
// 在此基础上，考虑每个 1 选择与否对答案的影响
for(int i=0;i<cnts[1];i++) res=res*2%MOD;
return res;
}
};