2022.02.22

1994.好子集的数目

https://leetcode-cn.com/problems/the-number-of-good-subsets/

给你一个整数数组 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 中不同的 好 子集的数目对 10^9 + 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 <= 105
1 <= nums[i] <= 30

&emsp;学到的知识点：状态压缩+动态规划
&emsp;这也能dp.jpg
&emsp;这个看到数据范围后将每个数字的因子的状态压缩为二进制数的方式确实很机智。
&emsp;不知道写点什么好（低情商：没理解透彻），放个题解链接吧。
&emsp;以及我直到AC完了还不知道题解为啥要倒序遍历mask，反正我没倒序。
&emsp;代码：（C++）

class Solution {
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        long int mod=1000000007;
        int primes[10]={2,3,5,7,11,13,17,19,23,29};
        int count[34]={0};
        int n=nums.size();
        int ans=0;
        for(int i=0;i<n;i++){
            count[nums[i]]++;
        }
        int mask=1<<10;
        long int f[1<<10]={1};
        for(int i=2;i<=30;i++){
            if(count[i]==0) continue;
            int masked_i=0;
            bool ok=true;
            int temp_i=i;
            for(int j=0;j<10;j++){
                int c=0;
                while(temp_i%primes[j]==0 && temp_i>1){
                    masked_i|=(1<<j);
                    c++;
                    temp_i/=primes[j];
                }
                if(c>1){
                    ok=false;
                    break;//当i内有某个因子多于2次时，这个i必不能用
                }
            }
            if(!ok) continue;
            for(int j=0;j<mask;j++){
                if(f[j]==0)continue;
                if((j & masked_i)==0){
                    f[j|masked_i]=(f[j|masked_i]+f[j]*count[i])%mod;
                }
            }
        }
        for(int i=1;i<mask;i++){
            ans=(ans+f[i])%mod;
        }
        for(int i=0;i<count[1];i++){
            ans=ans*2%mod;
        }
        return ans;
    }
};