【leetcode刷题第40天】1994.好子集的数目

本文主要是介绍【leetcode刷题第40天】1994.好子集的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第四十天

1994 好子集的数目

给你一个整数数组 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 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

方法

使用状态压缩dp来处理这个问题，首先我们得明确以下几点：

如果一个子集是好子集，那么我们对其中的每一个元素进行质因数分解，得到的最终结果就是题目中要求的互不相同的质数的乘积。换言之，对于4,9..等数，他们的质因数分解存在两个或以上相同的质因子，则不可能存在于好子集中。
对于1，其起到的作用可有可无，因为1和任何数相乘都不会发生变化，所以对于所有的1，其可取可不取，它的存在会使最终的结果翻 $2^{count[1]}$ 倍。
30以内的质数只有2,3,5,7,11,13,17,19,23,29这10个，最极端的情况是这10个数都出现一次，对于其他情况，我们对好子集进行质因数分解，只要上述各个质数出现的次数不多于1次，就是一个合法的情况。我们使用一个长度为10的二进制数来表示各个质数出现的情况，对于状态status，其第i位上的1表示第i个质数出现了一次。

我们定义dp[i]表示以i作为状态码的好子集的数量，例如dp[1024]，1024的二进制表示是1111111111，表示上述10个质数都出现了一次，它们所组成的乘积对应的好子集的数量。

考虑状态转移方程，对于一个数a，我们先预先统计出其出现的次数，然后将其转换为不同的质因数的积，将这些不同的质因数转换成一个subset，表示能够用这个数a能够引出来的状态。然后我们从a这个状态去转移，当一个status & subset = 0时，表明这个status能够由subset这个状态转移过来。

class Solution {public static final int MOD = 1000000007;public int numberOfGoodSubsets(int[] nums) {int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};int[] quantityOfNumberI = new int[31];for (int i : nums) quantityOfNumberI[i]++;long[] dp = new long[(1 << primes.length) + 1];dp[0] = 1;for (int i = 2; i <= 30; ++i) {if (quantityOfNumberI[i] == 0) continue;int subset = 0;boolean isValid = true;for (int j = 0; j < primes.length; ++j) {if (i % (primes[j] * primes[j]) == 0) {isValid = false;break;}if (i % primes[j] == 0) subset |= (1 << j);}if (isValid) {for (int mask = 1; mask <= (1 << primes.length); ++mask) {if ((mask & subset) == subset)dp[mask] = (dp[mask] % MOD + ((dp[mask ^ subset] % MOD) * quantityOfNumberI[i]) % MOD) % MOD;}}}long res = 0;for (int i = 1; i < dp.length; ++i) res = (res % MOD + dp[i] % MOD) % MOD;for (int i = 0; i < quantityOfNumberI[1]; ++i) res = (res * 2) % MOD;return (int) res;}
}