1994-好子集的数目(The Number of Good Subsets)

原文链接: https://leetcode-cn.com/problems/the-number-of-good-subsets

英文原文

You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.

For example, if nums = [1, 2, 3, 4]:

<ul>
    <li><code>[2, 3]</code>, <code>[1, 2, 3]</code>, and <code>[1, 3]</code> are <strong>good</strong> subsets with products <code>6 = 2*3</code>, <code>6 = 2*3</code>, and <code>3 = 3</code> respectively.</li>
    <li><code>[1, 4]</code> and <code>[4]</code> are not <strong>good</strong> subsets with products <code>4 = 2*2</code> and <code>4 = 2*2</code> respectively.</li>
</ul>
</li>

Return the number of different good subsets in nums modulo 10⁹ + 7.

A subset of nums is any array that can be obtained by deleting some (possibly none or all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

Example 1:

Input: nums = [1,2,3,4]
Output: 6
Explanation: The good subsets are:
- [1,2]: product is 2, which is the product of distinct prime 2.
- [1,2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [1,3]: product is 3, which is the product of distinct prime 3.
- [2]: product is 2, which is the product of distinct prime 2.
- [2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [3]: product is 3, which is the product of distinct prime 3.

Example 2:

Input: nums = [4,2,3,15]
Output: 5
Explanation: The good subsets are:
- [2]: product is 2, which is the product of distinct prime 2.
- [2,3]: product is 6, which is the product of distinct primes 2 and 3.
- [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5.
- [3]: product is 3, which is the product of distinct prime 3.
- [15]: product is 15, which is the product of distinct primes 3 and 5.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 30

中文题目

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以用若干个 互不相同的质数 相乘得到，那么我们称它为 好子集 。

比方说，如果 nums = [1, 2, 3, 4] ：

<ul>
    <li><code>[2, 3]</code>&nbsp;，<code>[1, 2, 3]</code>&nbsp;和&nbsp;<code>[1, 3]</code>&nbsp;是 <strong>好</strong>&nbsp;子集，乘积分别为&nbsp;<code>6 = 2*3</code>&nbsp;，<code>6 = 2*3</code>&nbsp;和&nbsp;<code>3 = 3</code>&nbsp;。</li>
    <li><code>[1, 4]</code> 和&nbsp;<code>[4]</code>&nbsp;不是 <strong>好</strong>&nbsp;子集，因为乘积分别为&nbsp;<code>4 = 2*2</code> 和&nbsp;<code>4 = 2*2</code>&nbsp;。</li>
</ul>
</li>

请你返回 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

通过代码

高赞题解

大家好，我是小爱，一个热爱算法并不断努力的女孩子！关注我，和我一起交流算法心得呀！

解法：状态压缩 + 预处理

题目要求，某个子集所有元素的乘积可以用若干个不同质数相乘得到，也就是说，该子集中，不能出现某个质数 $2$ 次及以上的幂次。

所以首先，我们可以排除自身就含有某质数高次幂的数字。例如，$4$ 中含有 $2$ 的二次幂，所以 $4$ 不能出现在任一“好子集”中。而 $4$ 的倍数 $8, 12, 16, 20, 24, 28$ 也不能出现在“好子集”中。同理，我们可以排除掉 $9, 16, 18, 25, 27$ 这五个数。

因此，$[1, 30]$ 中仅剩下 $19$ 个数字可能出现在题目要求的“好子集”中，我们将这些数存入数组 $all$ 中。特别地，每个数字都会出现若干次，将每个数及其出现的次数记录在数组中 $cnt$ 中。

其次，有些数字是不能同时出现在“好子集”中的。例如，$3$ 和 $6$ 均具有 $3$ 这个因子，如果同时出现，则子集中就会出现 $3$ 的二次幂，所以这两个数不能同时出现。拓展到一般情况，若两数的最大公约数大于 $1$，则这两个数不能同时出现。

根据前面的分析，根据 $n = 19$ 的数量级，我们可以考虑利用状态压缩，利用在 $O(n ·2^n)$ 的时间复杂度内解决本题。我们可以提前预处理出所有合法状态：在代码中，若某状态（一个 $19$ 位二进制数）合法，则其 valid 值为 $true$，否则为 $false$。

在此之后，我们便可以遍历所有状态 mask，并遍历 $n$ 个位置。若当前状态的二进制表示在位置 $i$ 上为 $1$ ，说明当前子集中要取 all[i] 这个数。我们需要分类讨论，若当前数字为 $1$，则可以取 $[1, cnt[1]]$ 中的任意数量，方式数为 $2^{cnt[i]} - 1$ 种。若当前数字不为 $1$，则只能取 $1$ 次，方式数为 $cnt[i]$。

特别地，一个子集中不能只含 $1$，所以，我们遍历 mask 时可以直接从 $mask = 2$ 开始。

代码：

class Solution {
    using ll = long long;
    const ll M = 1e9 + 7;
public:
    vector<int> all = {1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30};
    
    ll qpow(ll a, ll b, ll p) {
        ll ret = 1;
        while(b) {
            if(b & 1) ret = (ret * a) % p;
            a = (a * a) % p;
            b >>= 1;
        }
        return ret;
    }
    
    int numberOfGoodSubsets(vector<int>& nums) {
        int n = nums.size();
        vector<ll> cnt(31);
        for(int &x : nums) {
            // 仅记录可能出现的数字
            if(x % 4 == 0 || x % 9 == 0 || x == 25) continue;
            cnt[x]++;
        }

        // 预处理所有合法状态
        vector<bool> valid(1<<19, true);
        for(int i = 2; i < (1 << 19); i++) {
            if(i & (1 << 1)) {
                // 2
                if((i & (1 << 4)) || (i & (1 << 6)) || (i & (1 << 9)) || (i & (1 << 14)) || (i & (1 << 16)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 2)) {
                // 3
                if((i & (1 << 4)) || (i & (1 << 10)) || (i & (1 << 13)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 3)) {
                // 5
                if((i & (1 << 6)) || (i & (1 << 10)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 4)) {
                // 6
                if((i & (1 << 6)) || (i & (1 << 9)) || (i & (1 << 10)) || (i & (1 << 13)) || (i & (1 << 14)) || (i & (1 << 16)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 5)) {
                // 7
                if((i & (1 << 9)) || (i & (1 << 13))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 6)) {
                // 10
                if((i & (1 << 9)) || (i & (1 << 10)) || (i & (1 << 14)) || (i & (1 << 16)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 7)) {
                // 11
                if((i & (1 << 14))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 8)) {
                // 13
                if((i & (1 << 16))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 9)) {
                // 14
                if((i & (1 << 13)) || (i & (1 << 14)) || (i & (1 << 16)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 10)) {
                // 15
                if((i & (1 << 13)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 13)) {
                // 21
                if((i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 14)) {
                // 22
                if((i & (1 << 16)) || (i & (1 << 18))) {
                    valid[i] = false;
                }
            }
            if(i & (1 << 16)) {
                // 26
                if((i & (1 << 18))) {
                    valid[i] = false;
                }
            }
        }
        
        ll ret = 0;
        for(int mask = 2; mask < (1 << 19); ++mask) {
            // 当前状态合法
            if(valid[mask]) {
                ll ans = 1;
                for(int j = 0; j < 19; ++j) {
                    if(mask & (1 << j)) {
                        if(j == 0) {
                            // 当前数字为 1
                            ans = ans * ((qpow(2, cnt[all[j]], M) - 1 + M) % M) % M;
                        } else {
                            ans = ans * cnt[all[j]] % M;
                        }
                    }
                }
                ret = (ret + ans) % M;
            }
        }
        return ret;
    }
};

复杂度分析：

时间复杂度：$O(n·2^n)$
空间复杂度：$O(2^n)$

统计信息

通过次数	提交次数	AC比率
1314	3527	37.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途