Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Hardbitmask-dp

The Number of Good Subsets

Problem (yeniden ifade)

nums[i] ∈ [1,30]. Çarpımı karesiz olan (boş olmayan) indeks-alt kümelerini 10^9+7 modunda say.

Sezgi

On asal 10 bite sığar: 2,3,5,7,11,13,17,19,23,29. Kare çarpanlı sayılar (4,8,9,…) kullanılmaz. Kalan her x bir asal bitset’idir; ortak bit varsa çakışır. 1’ler çarpımı değiştirmez — sonda 2^{freq[1]} ile çarp.

Yaklaşımlar

Asal-maske DP

Doğrulanmadı

Zaman O(30 * 2^{10})Alan O(2^{10})

Fikir. dp[mask] = o asal kümesini kurma sayısı. Maskesi m olan her x için maskeleri geriden yürü, ayrıkken dp[mask] * freq[x]’i mask | m’ye ekle. Cevap (sum(dp) - 1) * 2^{freq[1]} (boş kümeyi düş; yalnız 1’ler başka sayı olmadan sayılmaz).

Yürüyüş. [1,2,3,4] → 6 (4 atılır; {2},{3},{2,3} her biri 1 ile veya onsuz). [4,4,4,5,6] → 3 ({5},{6},{5,6}).

Trade-off. Ters maske dolaşımı 0/1 knapsack hamlesidir; değer tür olarak bir kez, sıklığı çarpandır. C#’ta moddan önce long.

Çözüm

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;
}

Şablon bağlantısı

Alt küme seçim bitmask DP: öğeler karesiz sayılar, maliyet asal-bitset, çakışma = örtüşen bitler.

Yansıma

dp[mask] o asal kümesini kurma sayısı. Sayı karesiz asal maskesi taşır. Maskeler geriden yürür, kesişen asal eklenmez.
Cevap (toplam dp − 1) * 2^(freq[1]). Boş küme düşer. Yalnız 1’ler, başka sayı yoksa sayılmaz.
4 veya 9 gibi kare bölenli sayı hiç girmez. Mod. 1 her iyi kümeye serbest çarpan.