题目

题目链接
需要注意的题目细节：质数、互不重复、元素1如何处理、元素积

思路

思路1-排列组合

我们将符合"能够表示为不相同质数之积"的数字成为合法数字，30及以内的合法数字有2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30。

原始数组[1,2,3,4,5,15]

分析一般情况
[1,2]组成一个好子集，因为元素之积为2，可以表示为互不相同质数的积。此时对于新加入元素3进行判断，因为[1,2]的积为2，2与3最大公约数为1，所以将3加入[1,2]形成子集[1,2,3]也是好子集，我们可以得出规律与好子集的元素积的最大公约数为1的合法数字可以加入好子集形成新的好子集。
同时，最大公约数为1的条件也约束新形成的子集之积的质数分解不会有重复元素。因为题目设定相同元素只要下标不同就是不同元素，所以假设[1,2]共有3个，元素3有5个，那么好子集[1,2,3]的数量就是3*5=15个。
即新加入数字num数量为d1与原始数组ori元素积为x数量为d2，若num与x的最大公约数为1，则num可加入ori形成新的好子集，新的好子集的个数为原始元素积为num*x的好子集数量加上d1×d2。
分析特殊情况-数字1
因为数字1不是质数，所以单纯由数字1组成数组没有好子集，但任意数量数字1插入一个好子集仍然是好子集。
假设有三个1，因为题目要求下标不同元素不同，所以三个1有 $C_3^0+C_3^3+C_3^2+C_3^1=8$ 种排列组合（其中1是任何一个1都不加入好子集，及好子集本身的情况）。
由公式 $C_n^0+C_n^1+C_n^2+……+C_n^n = 2^n$ ，所以对于任一好子集与这三个1进行组合会有 $2^3\times sum(好子集)$ 个新好子集。
所以任一相同元素积的好子集的数量应该为原始相同元素积的好子集的个数× $2^{元素1的数量}$ 。
同时因为全是1的子集不是好子集，所以最后应该减去元素积为1的子集数量。

所以我们归纳出以下解题步骤：
第一步、首先将原始数组内不符合”能够表示为不相同质数之积“的数字去除，例如4，8，9等，并将原始数组与30以内合法数字去并集得到数组legal_nums
第二步、遍历legal_nums内所有合法数字num，对于dict所有已经加入的元素积x进行遍历判断，若当前循环合法数字与元素积最大公约数为1则可以形成新的好子集，新好子集数量为原始元素积为 $num\times x$ 的好子集数量加上合法数字的个数乘元素积为 $x$ 的好子集数量
第三步、将dict所有kv对的value值加和并减去元素积为1的子集个数，得到答案

思路2-状态压缩动态规划

待补充

Python3解法

"""
思路1-排列组合
"""
def numberOfGoodSubsets(self, nums: list[int]) -> int:
        ct, mod = Counter(nums), 10**9+7
        d = defaultdict(int)
        # 求1的数量d[1],然后计算2的d[1]次方
        d[1] = (1 << ct[1])
        # 求出给定数组nums当中合法的数字
        total_legal_nums = [2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30]
        # 取给定数组nums与30以内合法数字数组total_legal_nums的并集
        legal_nums = list(set(nums).intersection(set(total_legal_nums)))
        
        for num in legal_nums:
            for x in list(d):
                if math.gcd(num, x) == 1:
                    d[num*x] += ct[num]*d[x]
        return (sum(d.values())-d[1]) % mod

"""
思路2-状态压缩动态规划
"""
def numberOfGoodSubsets(self, nums: List[int]) -> int:
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        mod = 10**9 + 7
        freq = 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, i
            check = True
            for j, prime in enumerate(primes):
                if x % (prime * prime) == 0:
                    check = False
                    break
                if 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) % mod
        ans = sum(f[1:]) % mod
        return ans