好子集的数目

难度: Hard

给你一个整数数组 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⁹ + 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⁵
1 <= nums[i] <= 30

Submission

运行时间: 120 ms

内存: 21.2 MB

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        pri=[2,3,5,7,11,13,17,19,23,29]                
        dic=Counter(nums)
        #情况1只含质数
        cnt1=1
        for i in pri:
            cnt1*=(dic[i]+1)
        ans=cnt1-1
        #print(ans)
        def ct(a,b):
            cnt2=1
            for i in pri:
                if i!=a and i!=b:
                    cnt2*=(dic[i]+1)            
            return cnt2*dic[a*b]
        #情况2:一个合数 [6,10,14,15,21,22,26,30]  
        ans+=ct(2,3)+ct(2,5)+ct(2,7)+ct(3,5)+ct(3,7)+ct(2,11)+ct(2,13)
        #有30单独算
        cnt2=1
        for i in pri:
            if i!=2 and i!=3 and i!=5:
                cnt2*=(dic[i]+1)
        ans+=cnt2*dic[30] 
        #情况3:两个合数 [15,14][15,22][15,26][21,10][21,22][21,26]
        def cth(a,b,c,d):
            cnt3=1
            for i in pri:
                if i!=a and i!=b and i!=c and i!=d:
                    cnt3*=(dic[i]+1)            
            return cnt3*dic[a*b]*dic[c*d]
        
        ans+=cth(3,5,2,7)+cth(3,5,2,11)+cth(3,5,2,13)+cth(3,7,2,5)+cth(3,7,2,11)+cth(3,7,2,13)
        
        return (ans*(2**dic[1]))%(10**9+7)

Explain

此题解通过考虑不同类型的子集并分情况处理来计算好子集的数目。主要分为三类情况：1.只包含质数的子集；2.包含一个合数的子集；3.包含两个合数的子集。对于每种情况，分别计算可能的子集数量并求和。此外，1的存在对子集的组合方式有特殊影响，因为任何数量的1都可以添加到子集中而不改变乘积的质数组成，因此最后的结果需要乘上2的1的个数次幂。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        pri=[2,3,5,7,11,13,17,19,23,29]                # 定义质数列表
        dic=Counter(nums)  # 计算nums中每个数字的出现次数
        # 情况1: 只含质数
        cnt1=1
        for i in pri:
            cnt1*=(dic[i]+1)
        ans=cnt1-1  # 计算只包含质数的子集数目
        # 情况2: 包含一个合数
        def ct(a,b):
            cnt2=1
            for i in pri:
                if i!=a and i!=b:
                    cnt2*=(dic[i]+1)
            return cnt2*dic[a*b]
        ans+=ct(2,3)+ct(2,5)+ct(2,7)+ct(3,5)+ct(3,7)+ct(2,11)+ct(2,13)
        # 特殊情况: 包含数字30
        cnt2=1
        for i in pri:
            if i!=2 and i!=3 and i!=5:
                cnt2*=(dic[i]+1)
        ans+=cnt2*dic[30] 
        # 情况3: 包含两个合数
        def cth(a,b,c,d):
            cnt3=1
            for i in pri:
                if i!=a and i!=b and i!=c and i!=d:
                    cnt3*=(dic[i]+1)
            return cnt3*dic[a*b]*dic[c*d]
        ans+=cth(3,5,2,7)+cth(3,5,2,11)+cth(3,5,2,13)+cth(3,7,2,5)+cth(3,7,2,11)+cth(3,7,2,13)
        # 最后考虑1的影响
        return (ans*(2**dic[1]))%(10**9+7)  # 最终结果乘上1的可能组合数并取模

Explore

在解决问题的过程中，我预先定义了一个质数列表`pri`包含了所有小于30的质数。这样做是因为在给定的题目中，我们只关注数字30及以下的数字。通过这个列表，我们可以明确知道哪些数字是质数。对于合数的识别，由于题目只涉及到特定的合数（比如6、10、15等），所以我们通过组合列表中的质数来判断特定数字是否为合数。

数字1在计算好子集中需要特别处理，因为它是一个特殊的数字。1乘以任何数字的结果仍然是原数字，因此在形成子集时，1的存在不会改变子集乘积的质因数结构。这意味着任何一个有效的子集，我们都可以任意添加任意数量的1而不改变它作为好子集的资格。因此，在计算最终的子集数时，我们需要将所有不包含1的子集数乘以2的1的个数次幂，来包含所有可能加入1的情况。

在题解中，`ct`函数用于计算包含恰好一个特定合数的子集数。它首先计算除了该合数涉及的质因数外的所有质数的组合数量，然后乘以该合数的出现次数。`cth`函数则用于处理情况3，即子集中包含两个不同的合数。这个函数类似于`ct`，但它会排除两个合数涉及的所有质因数，并计算剩余质数的组合数量，然后乘以这两个合数的出现次数的乘积。这两个函数都是通过筛选和组合质数的方式，来计算在特定条件下的子集可能性。

模数`10**9+7`是一个常用的大质数，在竞赛和算法实现中广泛使用，主要是因为它足够大，可以防止计算结果在整数运算中溢出，同时又能保持计算的高效性。此外，由于它是质数，也便于在取模运算中保持数的分布均匀，减少潜在的冲突或偏差。使用此模数是为了保证结果的稳定性和正确性，同时符合编程实践中的标准。