题目
给你一个整数数组 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; } };
