Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardbitmask-dp

The Number of Good Subsets

Problem (restated)

nums[i] ∈ [1,30]. Count index-subsets whose product is square-free (non-empty), modulo 10^9+7.

Intuition

Ten primes fit in 10 bits: 2,3,5,7,11,13,17,19,23,29. Numbers with a squared factor (4,8,9,…) are unusable. Each remaining x is a bitset of primes; two numbers conflict if they share a bit. 1s do not change the product — multiply by 2^{freq[1]} at the end.

Approaches

Prime-mask DP

Unverified

Time O(30 * 2^{10})Space O(2^{10})

Idea. dp[mask] = ways to form that prime set. For each value x with mask m, walk masks backward and add dp[mask] * freq[x] into mask | m when they are disjoint. Answer (sum(dp) - 1) * 2^{freq[1]} (drop the empty set; lone 1s are not counted without another number).

Walkthrough. [1,2,3,4] → 6 (4 skipped; {2},{3},{2,3} each with or without the 1). [4,4,4,5,6] → 3 ({5},{6},{5,6}).

Trade-offs. Reverse-mask iteration is the 0/1 knapsack move so one value is used once as a type (its frequency is the multiplier). Use long before mod in C#.

Solution

const MOD = 1_000_000_007;
const PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];

function factorMask(x: number): number {
  let mask = 0;
  for (let i = 0; i < PRIMES.length; i++) {
    const p = PRIMES[i]!;
    if (x % p === 0) {
      x = Math.floor(x / p);
      if (x % p === 0) return -1;
      mask |= 1 << i;
    }
  }
  return x === 1 ? mask : -1;
}

export function numberOfGoodSubsets(nums: number[]): number {
  const freq = new Array<number>(31).fill(0);
  for (const x of nums) freq[x]! += 1;
  const dp = new Array<number>(1 << 10).fill(0);
  dp[0] = 1;
  for (let x = 2; x <= 30; x++) {
    if (!freq[x]) continue;
    const msk = factorMask(x);
    if (msk < 0) continue;
    for (let mask = (1 << 10) - 1; mask >= 0; mask--) {
      if (mask & msk) continue;
      dp[mask | msk] = (dp[mask | msk]! + dp[mask]! * freq[x]!) % MOD;
    }
  }
  let total = 0;
  for (const v of dp) total = (total + v) % MOD;
  let ones = 1;
  for (let i = 0; i < freq[1]!; i++) ones = (ones * 2) % MOD;
  return ((total - 1 + MOD) * ones) % MOD;
}

const MOD = 1_000_000_007;
const PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];

function factorMask(x: number): number {
  let mask = 0;
  for (let i = 0; i < PRIMES.length; i++) {
    const p = PRIMES[i]!;
    if (x % p === 0) {
      x = Math.floor(x / p);
      if (x % p === 0) return -1;
      mask |= 1 << i;
    }
  }
  return x === 1 ? mask : -1;
}

export function numberOfGoodSubsets(nums: number[]): number {
  const freq = new Array<number>(31).fill(0);
  for (const x of nums) freq[x]! += 1;
  const dp = new Array<number>(1 << 10).fill(0);
  dp[0] = 1;
  for (let x = 2; x <= 30; x++) {
    if (!freq[x]) continue;
    const msk = factorMask(x);
    if (msk < 0) continue;
    for (let mask = (1 << 10) - 1; mask >= 0; mask--) {
      if (mask & msk) continue;
      dp[mask | msk] = (dp[mask | msk]! + dp[mask]! * freq[x]!) % MOD;
    }
  }
  let total = 0;
  for (const v of dp) total = (total + v) % MOD;
  let ones = 1;
  for (let i = 0; i < freq[1]!; i++) ones = (ones * 2) % MOD;
  return ((total - 1 + MOD) * ones) % MOD;
}

Template connection

Subset-selection bitmask DP: items are square-free numbers, cost is the prime-bitset, conflict = overlapping bits.

Reflection

dp[mask] is the number of ways to build that set of primes. A square-free number carries a prime mask. Walk masks backward, and do not add a number that shares a prime.
The answer is (sum(dp) - 1) * 2**(freq[1]). The empty subset is dropped. Ones alone, with no other number, do not count.
A number divisible by a square, such as 4 or 9, never enters. Reduce modulo the usual prime. Each 1 is a free factor on every good subset.