Formatted question description: https://leetcode.ca/all/1994.html

# 1994. The Number of Good Subsets

## Level

Hard

## Description

You are given an integer array `nums`

. We call a subset of `nums`

**good** 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 different good subsets in nums modulo 10^9 + 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.

**Example 1:**

**Input:** nums = [1,2,3,4]

**Output:** 6

**Explanation:** The good subsets are:

**Example 2:**

**Input:** nums = [4,2,3,15]

**Output:** 5

**Explanation:** The good subsets are:

**Constraints:**

`1 <= nums.length <= 10^5`

`1 <= nums[i] <= 30`

## Solution

Use dynamic programming with compressed states. Obviously, each prime factor can occur at most once in a good subset, and if the number 1 is in `nums`

, the number 1 can occur any number of times as long as the subset contains at least one number that is greater than 1.

```
class Solution {
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
public int numberOfGoodSubsets(int[] nums) {
final int MODULO = 1000000007;
int length = nums.length;
int[] states = new int[31];
for (int i = 1; i <= 30; i++)
states[i] = calculate(i);
int[] f = new int[1 << 10];
int[] g = new int[1 << 10];
int[] counts = new int[31];
for (int i = 0; i < length; i++)
counts[nums[i]]++;
if (counts[1] == length)
return 0;
f[0] = 1;
for (int i = 2; i <= 30; i++) {
int state = states[i];
if (state == -1 || counts[i] == 0)
continue;
for (int j = 0; j < 1 << 10; j++)
g[j] = f[j];
for (int j = 0; j < 1 << 10; j++) {
if (g[j] != 0 && (j & state) == 0) {
f[j ^ state] += (int) ((long) g[j] * counts[i] % MODULO);
f[j ^ state] %= MODULO;
}
}
}
int power = 1;
for (int i = 0; i < counts[1]; i++)
power = power * 2 % MODULO;
long sum = 0;
for (int i = 0; i < 1 << 10; i++)
sum += f[i];
sum += MODULO - 1;
sum %= MODULO;
sum = sum * power % MODULO;
return (int) sum;
}
public int calculate(int num) {
int state = 0;
for (int i = 0; i < 10; i++) {
if (num % primes[i] == 0) {
if ((num / primes[i]) % primes[i] == 0)
return -1;
state |= 1 << i;
}
}
return state;
}
}
```