1994. 好子集的数目Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

[2, 3] ，[1, 2, 3] 和 [1, 3] 是好子集，乘积分别为 6 = 23 ，6 = 23 和 3 = 3 。
[1, 4] 和 [4] 不是好子集，因为乘积分别为 4 = 22 和 4 = 22 。请你返回 nums 中不同的好子集的数目对 109 + 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

# 思路

dp[i][j]表示只从前i个数里面选，且所选数的质因数集合是状态j的所有选法

# 解法

class Solution {

    private static int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

    private static final int MAXN = 10, MAXM = 35, MOD = (int) 1e9 + 7;

    private static int[] cnt = new int[MAXM], dp = new int[1 << MAXN], tmp = new int[MAXN];

    private static long qpow(long a, long b) {
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) ans = ans * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return ans;
    }

    public int numberOfGoodSubsets(int[] nums) {
        Arrays.fill(cnt, 0);
        Arrays.fill(dp, 0);
        int m = 0;
        for (int num : nums) {
            cnt[num]++;
            m = Math.max(m, num);
        }

        dp[0] = 1;
        for (int i = 2; i <= m; i++) {
            if (cnt[i] == 0) continue;
            boolean flag = true;
            int num = i, s = 0;
            Arrays.fill(tmp, 0);
            for (int j = 0; j < MAXN; j++) {
                if (num % primes[j] == 0) {
                    s |= 1 << j;
                    while (num % primes[j] == 0) {
                        tmp[j]++;
                        num /= primes[j];
                    }
                    if (tmp[j] > 1) {
                        flag = false;
                        break;
                    }
                }
            }

            if (flag) {
                for (int j = (1 << MAXN) - 1; j >= 0; j--) {
                    if ((j & s) < s) continue;
                    dp[j] = (int) ((dp[j] + (long) dp[j ^ s] * cnt[i]) % MOD);
                }
            }
        }

        int ans = 0;
        for (int i = 1; i < 1 << MAXN; i++) {
            ans = (ans + dp[i]) % MOD;
        }
        ans = (int) ((long) ans * qpow(2, cnt[1]) % MOD);
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

# 总结

分析出几种情况，然后分别对各个情况实现

#Java