The Number of Good Subsets

Problem#

Numbers in [1, 30]. Count non-empty subsets where the product can be expressed as a product of distinct primes. Mod 10⁹+7.

Examples#

[1,2,3,4] → 6

Constraints#

1 <= n <= 10^5.

Hints#

Hint 1

Primes ≤ 30 are 2,3,5,7,11,13,17,19,23,29 (10 primes). Each number ≤ 30 is either invalid (has a squared prime factor) or maps to a subset of those 10. 1 is special — multiplies the count by 2^cnt[1].

Approach#

Bitmask DP over the 10 primes. For each v in [2..30] that’s squarefree, get its prime mask. dp[mask] = number of subset selections whose union mask is mask. Update: for each value’s count, for each existing dp entry with no overlap, multiply and add. Final: sum dp over non-zero masks, multiply by 2^cnt[1].

Solution#

class Solution {
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        const int MOD = 1'000'000'007;
        vector<int> primes = {2,3,5,7,11,13,17,19,23,29};
        vector<int> mask(31, 0);
        for (int v = 2; v <= 30; ++v) {
            int m = 0, x = v;
            bool ok = true;
            for (int i = 0; i < 10; ++i) {
                int p = primes[i];
                if (x % p == 0) {
                    if ((x / p) % p == 0) { ok = false; break; } // p^2
                    m |= 1 << i;
                    x /= p;
                }
            }
            if (ok && x == 1) mask[v] = m;
            else mask[v] = -1;
        }
        vector<int> cnt(31, 0);
        for (int v : nums) ++cnt[v];

        vector<long long> dp(1 << 10, 0);
        dp[0] = 1;
        for (int v = 2; v <= 30; ++v) {
            if (mask[v] <= 0 || cnt[v] == 0) continue;
            int m = mask[v];
            long long c = cnt[v];
            vector<long long> nd = dp;
            for (int s = 0; s < (1 << 10); ++s) {
                if (dp[s] && (s & m) == 0) {
                    nd[s | m] = (nd[s | m] + dp[s] * c) % MOD;
                }
            }
            dp = nd;
        }
        long long ans = 0;
        for (int s = 1; s < (1 << 10); ++s) ans = (ans + dp[s]) % MOD;
        long long pow2 = 1;
        for (int i = 0; i < cnt[1]; ++i) pow2 = pow2 * 2 % MOD;
        return (int)(ans * pow2 % MOD);
    }
};

func numberOfGoodSubsets(nums []int) int {
  const MOD = 1000000007
  primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
  mask := make([]int, 31)
  for v := 2; v <= 30; v++ {
    m, x, ok := 0, v, true
    for i, p := range primes {
      if x%p == 0 {
        if (x/p)%p == 0 {
          ok = false
          break
        }
        m |= 1 << i
        x /= p
      }
    }
    if ok && x == 1 {
      mask[v] = m
    } else {
      mask[v] = -1
    }
  }
  cnt := make([]int, 31)
  for _, v := range nums {
    cnt[v]++
  }
  dp := make([]int64, 1<<10)
  dp[0] = 1
  for v := 2; v <= 30; v++ {
    if mask[v] <= 0 || cnt[v] == 0 {
      continue
    }
    m := mask[v]
    c := int64(cnt[v])
    nd := make([]int64, 1<<10)
    copy(nd, dp)
    for s := 0; s < (1 << 10); s++ {
      if dp[s] != 0 && (s&m) == 0 {
        nd[s|m] = (nd[s|m] + dp[s]*c) % MOD
      }
    }
    dp = nd
  }
  var ans int64
  for s := 1; s < (1 << 10); s++ {
    ans = (ans + dp[s]) % MOD
  }
  pow2 := int64(1)
  for i := 0; i < cnt[1]; i++ {
    pow2 = pow2 * 2 % MOD
  }
  return int(ans * pow2 % MOD)
}

from typing import List

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        mask = [-1] * 31
        for v in range(2, 31):
            m, x, ok = 0, v, True
            for i, p in enumerate(primes):
                if x % p == 0:
                    if (x // p) % p == 0:
                        ok = False
                        break
                    m |= 1 << i
                    x //= p
            if ok and x == 1:
                mask[v] = m
        cnt = [0] * 31
        for v in nums:
            cnt[v] += 1

        dp = [0] * (1 << 10)
        dp[0] = 1
        for v in range(2, 31):
            if mask[v] <= 0 or cnt[v] == 0:
                continue
            m = mask[v]
            c = cnt[v]
            nd = dp[:]
            for s in range(1 << 10):
                if dp[s] and (s & m) == 0:
                    nd[s | m] = (nd[s | m] + dp[s] * c) % MOD
            dp = nd
        ans = 0
        for s in range(1, 1 << 10):
            ans = (ans + dp[s]) % MOD
        pow2 = pow(2, cnt[1], MOD)
        return ans * pow2 % MOD

var numberOfGoodSubsets = function(nums) {
    const MOD = 1000000007n;
    const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    const mask = new Array(31).fill(-1);
    for (let v = 2; v <= 30; v++) {
        let m = 0, x = v, ok = true;
        for (let i = 0; i < primes.length; i++) {
            const p = primes[i];
            if (x % p === 0) {
                if (Math.floor(x / p) % p === 0) { ok = false; break; }
                m |= 1 << i;
                x = Math.floor(x / p);
            }
        }
        if (ok && x === 1) mask[v] = m;
    }
    const cnt = new Array(31).fill(0);
    for (const v of nums) cnt[v]++;

    let dp = new Array(1 << 10).fill(0n);
    dp[0] = 1n;
    for (let v = 2; v <= 30; v++) {
        if (mask[v] <= 0 || cnt[v] === 0) continue;
        const m = mask[v];
        const c = BigInt(cnt[v]);
        const nd = dp.slice();
        for (let s = 0; s < (1 << 10); s++) {
            if (dp[s] !== 0n && (s & m) === 0) {
                nd[s | m] = (nd[s | m] + dp[s] * c) % MOD;
            }
        }
        dp = nd;
    }
    let ans = 0n;
    for (let s = 1; s < (1 << 10); s++) ans = (ans + dp[s]) % MOD;
    let pow2 = 1n;
    for (let i = 0; i < cnt[1]; i++) pow2 = pow2 * 2n % MOD;
    return Number(ans * pow2 % MOD);
};

class Solution {
    public int numberOfGoodSubsets(int[] nums) {
        final int MOD = 1_000_000_007;
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        int[] mask = new int[31];
        Arrays.fill(mask, -1);
        for (int v = 2; v <= 30; v++) {
            int m = 0, x = v;
            boolean ok = true;
            for (int i = 0; i < primes.length; i++) {
                int p = primes[i];
                if (x % p == 0) {
                    if ((x / p) % p == 0) { ok = false; break; }
                    m |= 1 << i;
                    x /= p;
                }
            }
            if (ok && x == 1) mask[v] = m;
        }
        int[] cnt = new int[31];
        for (int v : nums) cnt[v]++;

        long[] dp = new long[1 << 10];
        dp[0] = 1;
        for (int v = 2; v <= 30; v++) {
            if (mask[v] <= 0 || cnt[v] == 0) continue;
            int m = mask[v];
            long c = cnt[v];
            long[] nd = dp.clone();
            for (int s = 0; s < (1 << 10); s++) {
                if (dp[s] != 0 && (s & m) == 0) {
                    nd[s | m] = (nd[s | m] + dp[s] * c) % MOD;
                }
            }
            dp = nd;
        }
        long ans = 0;
        for (int s = 1; s < (1 << 10); s++) ans = (ans + dp[s]) % MOD;
        long pow2 = 1;
        for (int i = 0; i < cnt[1]; i++) pow2 = pow2 * 2 % MOD;
        return (int) (ans * pow2 % MOD);
    }
}

function numberOfGoodSubsets(nums: number[]): number {
    const MOD: bigint = 1000000007n;
    const primes: number[] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    const mask: number[] = new Array(31).fill(-1);
    for (let v = 2; v <= 30; v++) {
        let m: number = 0, x: number = v, ok: boolean = true;
        for (let i = 0; i < primes.length; i++) {
            const p: number = primes[i];
            if (x % p === 0) {
                if (Math.floor(x / p) % p === 0) { ok = false; break; }
                m |= 1 << i;
                x = Math.floor(x / p);
            }
        }
        if (ok && x === 1) mask[v] = m;
    }
    const cnt: number[] = new Array(31).fill(0);
    for (const v of nums) cnt[v]++;

    let dp: bigint[] = new Array(1 << 10).fill(0n);
    dp[0] = 1n;
    for (let v = 2; v <= 30; v++) {
        if (mask[v] <= 0 || cnt[v] === 0) continue;
        const m: number = mask[v];
        const c: bigint = BigInt(cnt[v]);
        const nd: bigint[] = dp.slice();
        for (let s = 0; s < (1 << 10); s++) {
            if (dp[s] !== 0n && (s & m) === 0) {
                nd[s | m] = (nd[s | m] + dp[s] * c) % MOD;
            }
        }
        dp = nd;
    }
    let ans: bigint = 0n;
    for (let s = 1; s < (1 << 10); s++) ans = (ans + dp[s]) % MOD;
    let pow2: bigint = 1n;
    for (let i = 0; i < cnt[1]; i++) pow2 = pow2 * 2n % MOD;
    return Number(ans * pow2 % MOD);
}

Editorial#

Each value 2..30 maps to a 10-bit prime-mask if squarefree. Subset products are squarefree iff the chosen masks are pairwise disjoint — bitmask DP exactly captures that. 1s freely double the count.

Complexity#

Time: O(n + 30 × 2^10).
Space: O(2^10).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#