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^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 <= 10^5
  • 1 <= nums[i] <= 30

解题思路

解题思路

这道题的关键在于理解"好子集"的定义：子集中所有元素的乘积可以表示为互不相同质数的乘积。

核心观察

  1. 范围限制：由于 nums[i] <= 30，我们只需要考虑 30 以内的质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29，共 10 个质数。

  2. 无效数字：包含重复质因数的数字（如 4=2², 8=2³, 9=3², 12=2²×3 等）不能构成好子集，需要排除。

  3. 状态压缩：用 10 位二进制数表示当前使用了哪些质数，每个位对应一个质数的使用状态。

算法流程

  1. 预处理：

    • 统计每个数字的出现次数
    • 为每个有效数字计算其质数掩码（哪些质数被使用）
    • 特殊处理数字 1（可以任意添加到好子集中）

  2. 动态规划：

    • dp[mask] 表示使用质数集合为 mask 的好子集数量
    • 对每个有效数字，尝试将其添加到所有兼容的状态中
    • 兼容条件：当前状态的质数集合与数字的质数集合无交集

  3. 结果计算：

    • 所有非空状态的好子集数量之和
    • 每个好子集都可以任意添加数字 1，所以要乘以 2^count[1]

时间复杂度：O(n + 2^10 × 有效数字种类数)，空间复杂度：O(1)。

代码实现

class Solution {
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        
        // 统计每个数字的出现次数
        vector<int> count(31, 0);
        for (int num : nums) {
            count[num]++;
        }
        
        // 获取数字的质数掩码
        auto getMask = [&](int num) -> int {
            int mask = 0;
            for (int i = 0; i < 10; i++) {
                int cnt = 0;
                while (num % primes[i] == 0) {
                    num /= primes[i];
                    cnt++;
                }
                if (cnt > 1) return -1; // 有重复质因数
                if (cnt == 1) mask |= (1 << i);
            }
            return num == 1 ? mask : -1; // num != 1 说明有大于29的质因数
        };
        
        // dp[mask] 表示质数集合为mask的好子集数量
        vector<long long> dp(1024, 0);
        dp[0] = 1;
        
        for (int num = 2; num <= 30; num++) {
            if (count[num] == 0) continue;
            
            int mask = getMask(num);
            if (mask == -1) continue; // 无效数字
            
            // 从高位到低位遍历，避免重复计算
            for (int state = 1023; state >= 0; state--) {
                if ((state & mask) == 0) { // 没有冲突的质数
                    dp[state | mask] = (dp[state | mask] + dp[state] * count[num]) % MOD;
                }
            }
        }
        
        // 计算结果
        long long result = 0;
        for (int mask = 1; mask < 1024; mask++) {
            result = (result + dp[mask]) % MOD;
        }
        
        // 每个好子集都可以任意添加数字1
        for (int i = 0; i < count[1]; i++) {
            result = (result * 2) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        
        # 统计每个数字的出现次数
        count = [0] * 31
        for num in nums:
            count[num] += 1
        
        # 获取数字的质数掩码
        def get_mask(num):
            mask = 0
            for i, prime in enumerate(primes):
                cnt = 0
                while num % prime == 0:
                    num //= prime
                    cnt += 1
                if cnt > 1:
                    return -1  # 有重复质因数
                if cnt == 1:
                    mask |= (1 << i)
            return mask if num == 1 else -1  # num != 1 说明有大于29的质因数
        
        # dp[mask] 表示质数集合为mask的好子集数量
        dp = [0] * 1024
        dp[0] = 1
        
        for num in range(2, 31):
            if count[num] == 0:
                continue
            
            mask = get_mask(num)
            if mask == -1:
                continue  # 无效数字
            
            # 从高位到低位遍历，避免重复计算
            for state in range(1023, -1, -1):
                if (state & mask) == 0:  # 没有冲突的质数
                    dp[state | mask] = (dp[state | mask] + dp[state] * count[num]) % MOD
        
        # 计算结果
        result = sum(dp[1:]) % MOD
        
        # 每个好子集都可以任意添加数字1
        result = (result * pow(2, count[1], MOD)) % MOD
        
        return result

public class Solution {
    public int NumberOfGoodSubsets(int[] nums) {
        const int MOD = 1000000007;
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        
        // 统计每个数字的出现次数
        int[] count = new int[31];
        foreach (int num in nums) {
            count[num]++;
        }
        
        // 获取数字的质数掩码
        int GetMask(int num) {
            int mask = 0;
            for (int i = 0; i < 10; i++) {
                int cnt = 0;
                while (num % primes[i] == 0) {
                    num /= primes[i];
                    cnt++;
                }
                if (cnt > 1) return -1; // 有重复质因数
                if (cnt == 1) mask |= (1 << i);
            }
            return num == 1 ? mask : -1; // num != 1 说明有大于29的质因数
        }
        
        // dp[mask] 表示质数集合为mask的好子集数量
        long[] dp = new long[1024];
        dp[0] = 1;
        
        for (int num = 2; num <= 30; num++) {
            if (count[num] == 0) continue;
            
            int mask = GetMask(num);
            if (mask == -1) continue; // 无效数字
            
            // 从高位到低位遍历，避免重复计算
            for (int state = 1023; state >= 0; state--) {
                if ((state & mask) == 0) { // 没有冲突的质数
                    dp[state | mask] = (dp[state | mask] + dp[state] * count[num]) % MOD;
                }
            }
        }
        
        // 计算结果
        long result = 0;
        for (int mask = 1; mask < 1024; mask++) {
            result = (result + dp[mask]) % MOD;
        }
        
        // 每个好子集都可以任意添加数字1
        for (int i = 0; i < count[1]; i++) {
            result = (result * 2) % MOD;
        }
        
        return (int)result;
    }
}

var numberOfGoodSubsets = function(nums) {
    const MOD = 1e9 + 7;
    const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    const validNums = [2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30];
    
    const getMask = (num) => {
        let mask = 0;
        for (let i = 0; i < primes.length; i++) {
            if (num % primes[i] === 0) {
                if (num % (primes[i] * primes[i]) === 0) return -1;
                mask |= (1 << i);
            }
        }
        return mask;
    };
    
    const count = new Array(31).fill(0);
    for (const num of nums) {
        count[num]++;
    }
    
    const dp = new Array(1024).fill(0);
    dp[0] = 1;
    
    for (const num of validNums) {
        if (count[num] === 0) continue;
        const mask = getMask(num);
        if (mask === -1) continue;
        
        for (let state = 1023; state >= 0; state--) {
            if (dp[state] === 0 || (state & mask) !== 0) continue;
            dp[state | mask] = (dp[state | mask] + dp[state] * count[num]) % MOD;
        }
    }
    
    let result = 0;
    for (let i = 1; i < 1024; i++) {
        result = (result + dp[i]) % MOD;
    }
    
    let power = 1;
    for (let i = 0; i < count[1]; i++) {
        power = (power * 2) % MOD;
    }
    
    return (result * power) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + 2^10 × k)n 为数组长度，k 为有效数字种类数（最多 10 种），2^10 = 1024
空间复杂度O(1)使用固定大小的数组，不随输入规模变化

相关题目