You are given an integer array nums. We call a subset of numsgood if its product can be represented as a product of one or more distinct prime numbers.
For example, if nums = [1, 2, 3, 4]:
[2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.
[1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 2*2 respectively.
Return _the number of differentgood subsets in _nums _modulo _109 + 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.
Input: nums =[1,2,3,4]Output: 6Explanation: The good subsets are:-[1,2]: product is2, which is the product of distinct prime 2.-[1,2,3]: product is6, which is the product of distinct primes 2 and 3.-[1,3]: product is3, which is the product of distinct prime 3.-[2]: product is2, which is the product of distinct prime 2.-[2,3]: product is6, which is the product of distinct primes 2 and 3.-[3]: product is3, which is the product of distinct prime 3.
Input: nums =[4,2,3,15]Output: 5Explanation: The good subsets are:-[2]: product is2, which is the product of distinct prime 2.-[2,3]: product is6, which is the product of distinct primes 2 and 3.-[2,15]: product is30, which is the product of distinct primes 2,3, and 5.-[3]: product is3, which is the product of distinct prime 3.-[15]: product is15, which is the product of distinct primes 3 and 5.
We use bitmask dynamic programming to count subsets whose product is a product of distinct primes (i.e., square-free). We skip numbers with repeated prime factors. For each valid number, we update the DP for all compatible masks. The answer is multiplied by the number of 1’s in the input, as 1 can be included or not in any subset.
#include<vector>usingnamespace std;
classSolution {
public:int numberOfGoodSubsets(vector<int>& nums) {
constint MOD =1e9+7;
vector<int> primes = {2,3,5,7,11,13,17,19,23,29};
vector<int> cnt(31);
for (int x : nums) ++cnt[x];
vector<int> mask(31);
for (int i =2; i <=30; ++i) {
int m =0, x = i, ok =1;
for (int j =0; j < primes.size(); ++j) {
int p = primes[j], c =0;
while (x % p ==0) { x /= p; ++c; }
if (c >1) ok =0;
if (c) m |=1<< j;
}
if (ok && x ==1) mask[i] = m;
}
vector<int> dp(1<<10);
dp[0] =1;
for (int i =2; i <=30; ++i) {
if (!mask[i] ||!cnt[i]) continue;
for (int s = (1<<10)-1; s >=0; --s) {
if ((s & mask[i]) ==0)
dp[s|mask[i]] = (dp[s|mask[i]] + (longlong)dp[s] * cnt[i]) % MOD;
}
}
longlong res =0, pow1 =1;
for (int s =1; s < (1<<10); ++s) res = (res + dp[s]) % MOD;
for (int i =0; i < cnt[1]; ++i) pow1 = pow1 *2% MOD;
return res * pow1 % MOD;
}
};
import java.util.*;
classSolution {
publicintnumberOfGoodSubsets(int[] nums) {
int MOD = 1_000_000_007;
int[] primes = {2,3,5,7,11,13,17,19,23,29};
int[] cnt =newint[31];
for (int x : nums) cnt[x]++;
int[] mask =newint[31];
for (int i = 2; i <= 30; ++i) {
int m = 0, x = i, ok = 1;
for (int j = 0; j < primes.length; ++j) {
int p = primes[j], c = 0;
while (x % p == 0) { x /= p; ++c; }
if (c > 1) ok = 0;
if (c > 0) m |= 1 << j;
}
if (ok == 1 && x == 1) mask[i]= m;
}
int[] dp =newint[1<<10];
dp[0]= 1;
for (int i = 2; i <= 30; ++i) {
if (mask[i]== 0 || cnt[i]== 0) continue;
for (int s = (1<<10)-1; s >= 0; --s) {
if ((s & mask[i]) == 0)
dp[s|mask[i]]= (int)((dp[s|mask[i]]+ (long)(dp[s]) * cnt[i]) % MOD);
}
}
long res = 0, pow1 = 1;
for (int s = 1; s < (1<<10); ++s) res = (res + dp[s]) % MOD;
for (int i = 0; i < cnt[1]; ++i) pow1 = pow1 * 2 % MOD;
return (int)(res * pow1 % MOD);
}
}
from typing import List
classSolution:
defnumberOfGoodSubsets(self, nums: List[int]) -> int:
MOD =10**9+7 primes = [2,3,5,7,11,13,17,19,23,29]
cnt = [0]*31for x in nums:
cnt[x] +=1 mask = [0]*31for i in range(2, 31):
m, x, ok =0, i, Truefor j, p in enumerate(primes):
c =0while x % p ==0:
x //= p
c +=1if c >1:
ok =Falseif c:
m |=1<< j
if ok and x ==1:
mask[i] = m
dp = [0] * (1<<10)
dp[0] =1for i in range(2, 31):
ifnot mask[i] ornot cnt[i]: continuefor s in range((1<<10)-1, -1, -1):
if (s & mask[i]) ==0:
dp[s|mask[i]] = (dp[s|mask[i]] + dp[s] * cnt[i]) % MOD
res = sum(dp[1:]) % MOD
pow1 = pow(2, cnt[1], MOD)
return res * pow1 % MOD
impl Solution {
pubfnnumber_of_good_subsets(nums: Vec<i32>) -> i32 {
let primes = [2,3,5,7,11,13,17,19,23,29];
letmut cnt =vec![0; 31];
for&x in&nums { cnt[x asusize] +=1; }
letmut mask =vec![0; 31];
for i in2..=30 {
letmut m =0;
letmut x = i;
letmut ok =true;
for (j, &p) in primes.iter().enumerate() {
letmut c =0;
while x % p ==0 {
x /= p;
c +=1;
}
if c >1 { ok =false; }
if c >0 { m |=1<< j; }
}
if ok && x ==1 { mask[i] = m; }
}
letmut dp =vec![0i64; 1<<10];
dp[0] =1;
for i in2..=30 {
if mask[i] ==0|| cnt[i] ==0 { continue; }
for s in (0..1<<10).rev() {
if (s & mask[i]) ==0 {
dp[s|mask[i]] = (dp[s|mask[i]] + dp[s] * cnt[i] asi64) %1_000_000_007;
}
}
}
letmut res =0i64;
for s in1..(1<<10) { res = (res + dp[s]) %1_000_000_007; }
letmut pow1 =1i64;
for _ in0..cnt[1] { pow1 = pow1 *2%1_000_000_007; }
(res * pow1 %1_000_000_007) asi32 }
}