You are given a positive integer 0-indexed array nums.
A subset of the array nums is square-free if the product of its elements is a square-free integer.
A square-free integer is an integer that is divisible by no square number other than 1.
Return the number of square-free non-empty subsets of the array nums. Since the answer may be too large, return it modulo 109 + 7.
A non-empty subset of nums is an array that can be obtained by deleting some (possibly none but not all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.
Example 1:
Input: nums = [3,4,4,5] Output: 3 Explanation: There are 3 square-free subsets in this example: - The subset consisting of the 0th element [3]. The product of its elements is 3, which is a square-free integer. - The subset consisting of the 3rd element [5]. The product of its elements is 5, which is a square-free integer. - The subset consisting of 0th and 3rd elements [3,5]. The product of its elements is 15, which is a square-free integer. It can be proven that there are no more than 3 square-free subsets in the given array.
Example 2:
Input: nums = [1] Output: 1 Explanation: There is 1 square-free subset in this example: - The subset consisting of the 0th element [1]. The product of its elements is 1, which is a square-free integer. It can be proven that there is no more than 1 square-free subset in the given array.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 30
Note that in the problem, the range of
In the subset without square numbers, the product of all elements can be represented as the product of one or more distinct prime numbers, that is, each prime factor can appear at most once. Therefore, we can use a binary number to represent the prime factors in a subset, where the
We can use the method of state compression dynamic programming to solve this problem. Let
We enumerate a number
Note that we did not start enumerating from the number
The time complexity is
Similar problems:
class Solution:
def squareFreeSubsets(self, nums: List[int]) -> int:
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
cnt = Counter(nums)
mod = 10**9 + 7
n = len(primes)
f = [0] * (1 << n)
f[0] = pow(2, cnt[1])
for x in range(2, 31):
if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
continue
mask = 0
for i, p in enumerate(primes):
if x % p == 0:
mask |= 1 << i
for state in range((1 << n) - 1, 0, -1):
if state & mask == mask:
f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod
return sum(v for v in f) % mod - 1class Solution {
public int squareFreeSubsets(int[] nums) {
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int[] cnt = new int[31];
for (int x : nums) {
++cnt[x];
}
final int mod = (int) 1e9 + 7;
int n = primes.length;
long[] f = new long[1 << n];
f[0] = 1;
for (int i = 0; i < cnt[1]; ++i) {
f[0] = (f[0] * 2) % mod;
}
for (int x = 2; x < 31; ++x) {
if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
continue;
}
int mask = 0;
for (int i = 0; i < n; ++i) {
if (x % primes[i] == 0) {
mask |= 1 << i;
}
}
for (int state = (1 << n) - 1; state > 0; --state) {
if ((state & mask) == mask) {
f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
}
}
}
long ans = 0;
for (int i = 0; i < 1 << n; ++i) {
ans = (ans + f[i]) % mod;
}
ans -= 1;
return (int) ans;
}
}class Solution {
public:
int squareFreeSubsets(vector<int>& nums) {
int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int cnt[31]{};
for (int& x : nums) {
++cnt[x];
}
int n = 10;
const int mod = 1e9 + 7;
vector<long long> f(1 << n);
f[0] = 1;
for (int i = 0; i < cnt[1]; ++i) {
f[0] = f[0] * 2 % mod;
}
for (int x = 2; x < 31; ++x) {
if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
continue;
}
int mask = 0;
for (int i = 0; i < n; ++i) {
if (x % primes[i] == 0) {
mask |= 1 << i;
}
}
for (int state = (1 << n) - 1; state; --state) {
if ((state & mask) == mask) {
f[state] = (f[state] + 1LL * cnt[x] * f[state ^ mask]) % mod;
}
}
}
long long ans = -1;
for (int i = 0; i < 1 << n; ++i) {
ans = (ans + f[i]) % mod;
}
return ans;
}
};func squareFreeSubsets(nums []int) (ans int) {
primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
cnt := [31]int{}
for _, x := range nums {
cnt[x]++
}
const mod int = 1e9 + 7
n := 10
f := make([]int, 1<<n)
f[0] = 1
for i := 0; i < cnt[1]; i++ {
f[0] = f[0] * 2 % mod
}
for x := 2; x < 31; x++ {
if cnt[x] == 0 || x%4 == 0 || x%9 == 0 || x%25 == 0 {
continue
}
mask := 0
for i, p := range primes {
if x%p == 0 {
mask |= 1 << i
}
}
for state := 1<<n - 1; state > 0; state-- {
if state&mask == mask {
f[state] = (f[state] + f[state^mask]*cnt[x]) % mod
}
}
}
ans = -1
for _, v := range f {
ans = (ans + v) % mod
}
return
}function squareFreeSubsets(nums: number[]): number {
const primes: number[] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
const cnt: number[] = Array(31).fill(0);
for (const x of nums) {
++cnt[x];
}
const mod: number = Math.pow(10, 9) + 7;
const n: number = primes.length;
const f: number[] = Array(1 << n).fill(0);
f[0] = 1;
for (let i = 0; i < cnt[1]; ++i) {
f[0] = (f[0] * 2) % mod;
}
for (let x = 2; x < 31; ++x) {
if (cnt[x] === 0 || x % 4 === 0 || x % 9 === 0 || x % 25 === 0) {
continue;
}
let mask: number = 0;
for (let i = 0; i < n; ++i) {
if (x % primes[i] === 0) {
mask |= 1 << i;
}
}
for (let state = (1 << n) - 1; state > 0; --state) {
if ((state & mask) === mask) {
f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
}
}
}
let ans: number = 0;
for (let i = 0; i < 1 << n; ++i) {
ans = (ans + f[i]) % mod;
}
ans -= 1;
return ans >= 0 ? ans : ans + mod;
}