class Solution {
public:
int numberOfGoodSubsets(vector<int>& nums) {
}
};
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 中不同的 好 子集的数目对 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 <= 1051 <= nums[i] <= 30原站题解
java 解法, 执行用时: 55 ms, 内存消耗: 57.7 MB, 提交时间: 2023-06-12 09:59:43
class Solution {
private static final int[] PRIMES = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
private static final int MOD = (int)1e9 + 7;
private static final Set<Integer> FORBID = new HashSet<>();
private static final int LEN_POWER = 1 << PRIMES.length;
static {
for(int i = 0; i < 3; i++)
for(int j = PRIMES[i] * PRIMES[i]; j <= 30; j += PRIMES[i] * PRIMES[i])
FORBID.add(j);
}
public int numberOfGoodSubsets(int[] nums) {
Map<Integer, Integer> cnts = new HashMap<>();
for(int num: nums)
if(!FORBID.contains(num))
cnts.put(num, cnts.getOrDefault(num, 0) + 1);
Map<Integer, Integer> keyPrimes = new HashMap<>();
for(int num: cnts.keySet()) {
int cur = 0;
for(int i = 0; i < PRIMES.length; i++)
if(num % PRIMES[i] == 0)
cur |= 1 << i;
keyPrimes.put(num, cur);
}
int[] dp = new int[LEN_POWER];
dp[0] = qpow(2, cnts.getOrDefault(1, 0), (long)MOD);
for(int i = 2; i <= 30; i++) {
if(cnts.containsKey(i))
for(int j = LEN_POWER - 1; j > 0; j--) {
int cur = keyPrimes.get(i);
if((cur & j) == cur) {
dp[j] = (dp[j] + (int)((long)cnts.get(i) * (long)dp[j ^ cur] % MOD)) % MOD;
}
}
}
int ans = 0;
for(int j = 1; j < LEN_POWER; j++)
ans = (ans + dp[j]) % MOD;
return ans;
}
int qpow(int a, int n, long mod){
long ans = 1, la = (long)a;
while(n > 0){
if((n&1) == 1)
ans = ans * la % mod;
la = la * la % MOD;
n >>= 1;
}
return (int)ans;
}
}
python3 解法, 执行用时: 544 ms, 内存消耗: 31.8 MB, 提交时间: 2023-06-12 09:59:13
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
FORBID = [p * p for p in PRIMES[:3]]
MOD = int(1e9 + 7)
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
cnts = Counter(nums)
for k in list(cnts.keys()):
for f in FORBID:
if not k % f:
cnts.pop(k)
key_primes = defaultdict(set)
for k in cnts:
for p in PRIMES:
if not k % p:
key_primes[k].add(p)
elif k < p:
break
ones = pow(2, cnts[1], MOD)
@lru_cache(None)
def dfs(idx, ps):
if idx > 30 or len(ps) == len(PRIMES):
# 不可能所有质数都没被选的空集
return (len(ps) > 0) * ones
st, ans = set(ps), 0
# idx存在在原数组中且质因子尚未被选
if idx in cnts and not key_primes[idx] & st:
ans += cnts[idx] % MOD * dfs(idx + 1, tuple(st | key_primes[idx])) % MOD
# 叠加不选idx的答案数
return (ans + dfs(idx + 1, ps)) % MOD
return dfs(2, tuple())
golang 解法, 执行用时: 304 ms, 内存消耗: 8.2 MB, 提交时间: 2023-06-12 09:58:49
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
func numberOfGoodSubsets(nums []int) (ans int) {
const mod int = 1e9 + 7
freq := [31]int{}
for _, num := range nums {
freq[num]++
}
f := make([]int, 1<<len(primes))
f[0] = 1
for i := 0; i < freq[1]; i++ {
f[0] = f[0] * 2 % mod
}
next:
for i := 2; i < 31; i++ {
if freq[i] == 0 {
continue
}
// 检查 i 的每个质因数是否均不超过 1 个
subset := 0
for j, prime := range primes {
if i%(prime*prime) == 0 {
continue next
}
if i%prime == 0 {
subset |= 1 << j
}
}
// 动态规划
for mask := 1 << len(primes); mask > 0; mask-- {
if mask&subset == subset {
f[mask] = (f[mask] + f[mask^subset]*freq[i]) % mod
}
}
}
for _, v := range f[1:] {
ans = (ans + v) % mod
}
return
}
python3 解法, 执行用时: 288 ms, 内存消耗: 20.9 MB, 提交时间: 2023-06-12 09:58:27
'''
定义 f[i][mask] 表示当我们只选择 [2,i] 范围内的数，
并且选择的数的质因数使用情况为 mask 时的方案数。
如果 i 本身包含平方因子，那么我们无法选择 i，
相当于在 [2,i−1] 范围内选择，状态转移方程为：f[i][mask]=f[i−1][mask]
如果 i 本身不包含平方因子，记其包含的质因子的二进制表示为 subset（同样可以通过试除的方法得到），
那么状态转移方程为：
f[i][mask]=f[i−1][mask]+f[i−1][mask\subset]×freq[i]
freq[i] 表示数组 nums 中 i 出现的次数；
mask\subset 表示从二进制表示 mask 中去除所有在 subset 中出现的 1，
可以使用按位异或运算实现。
'''
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
mod = 10**9 + 7
freq = Counter(nums)
f = [0] * (1 << len(primes))
f[0] = pow(2, freq[1], mod)
for i, occ in freq.items():
if i == 1:
continue
# 检查 i 的每个质因数是否均不超过 1 个
subset, x = 0, i
check = True
for j, prime in enumerate(primes):
if x % (prime * prime) == 0:
check = False
break
if x % prime == 0:
subset |= (1 << j)
if not check:
continue
# 动态规划
for mask in range((1 << len(primes)) - 1, 0, -1):
if (mask & subset) == subset:
f[mask] = (f[mask] + f[mask ^ subset] * occ) % mod
ans = sum(f[1:]) % mod
return ans