1994.好子集的数目.md

1994.好子集的数目

/*
 * @lc app=leetcode.cn id=1994 lang=typescript
 *
 * [1994] 好子集的数目
 */

// @lc code=start
function numberOfGoodSubsets(nums: number[]): number {}
// @lc code=end

解法 1: 动态规划

对于有可能超出安全数的计算,推荐用 BigInt,虽然 BigInt 并不是常数的时间复杂度,数越大时,处理的时间会越长,但只要每次操作进行取余,就能保证数是在 MOD 的范围内,这样的时间是可以接受的

function numberOfGoodSubsets(nums: number[]): number {
  const MOD = 10n ** 9n + 7n
  const add = (a: bigint, b: bigint) => (a + b) % MOD

  const set = new Set<number>(),
    map = new Map<number, number>(),
    counts = new Map<number, bigint>(),
    primes = new Set([1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
  for (const num of nums) {
    counts.set(num, (counts.get(num) ?? 0n) + 1n)
    set.add(num)
  }

  next: for (const num of set) {
    if (num === 1) continue
    let tmp = num,
      state = 0
    for (let i = 2; i <= tmp; i++) {
      if (!(tmp % i)) {
        if (!primes.has(i)) continue next
        state |= 1 << i
        tmp = tmp / i
      }
      if (!(tmp % i)) continue next
    }
    map.set(num, state)
  }
  let dp = new Map<number, bigint>([[0, 1n]])

  for (const [num, primeState] of map) {
    for (let [state, count] of dp) {
      if (state & primeState) continue
      let newState = state | primeState
      dp.set(newState, add(dp.get(newState) ?? 0n, count * counts.get(num)!))
    }
  }
  let res = 0n,
    one = counts.get(1) ?? 0n
  for (const [, count] of dp) {
    res = add(res, count)
  }

  return Number(((res - 1n) * 2n ** one) % MOD)
}

解法 2: 回溯

• 思路参考: 回溯+状态压缩+剪枝+位运算

function numberOfGoodSubsets(nums: number[]): number {
  const MOD = BigInt(10 ** 9 + 7)

  const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
  const primeMap = new Map<number, Set<number>>(primes.map(num => [num, new Set([num])]))
  // 统计拥有公共因子的集合
  const dfs = (start = 0, path: number[] = [], product = 1) => {
    if (product > 30 || start === nums.length) return
    for (let i = start; i < primes.length; i++) {
      if (product * primes[i] <= 30) {
        path.push(primes[i])
        for (const num of path) {
          primeMap.get(num)?.add(product * primes[i])
        }

        dfs(i + 1, path, product * primes[i])
        path.pop()
      }
      dfs(i + 1, path, product)
    }
  }
  dfs()

  // 标记每个数字对应互斥的状态
  const mutex = new Array(30).fill(0)
  for (const [, set] of primeMap) {
    let mask = 0
    for (const num of set) {
      mask |= 1 << num
    }
    for (const num of set) {
      mutex[num] = mutex[num] | mask
    }
  }

  // 统计每个数出现的次数,只保留质数,以及能有若干个不同质数相乘得到的数字
  const numMap = new Map<number, number>()
  for (const num of nums) {
    if (!mutex[num] && num !== 1) {
      continue
    }
    numMap.set(num, (numMap.get(num) ?? 0) + 1)
  }

  // 使用回溯算法,统计所有可能的结果
  // 对于当前数字可以取或不取
  // 不过只有当之前没有跟当前数字有互斥状态时,才能取当前数字
  // 进行取余时,需要先转换成 BigInt,否则会出现溢出导致结果不准确
  const dfs1 = (i = 2, cur = 0): number => {
    if (i > 30) {
      return cur > 0 ? 1 : 0
    }
    let res = 0
    res = res + dfs1(i + 1, cur)
    if (numMap.has(i) && (mutex[i] & cur) === 0) {
      res = res + dfs1(i + 1, cur | (1 << i)) * numMap.get(i)!
    }

    return Number(BigInt(res) % MOD)
  }

  let res = dfs1()
  if (numMap.get(1)) {
    res = Number((BigInt(res) * BigInt(2) ** BigInt(numMap.get(1)!)) % BigInt(MOD))
  }

  return res
}

Case

test.each([
  { input: { nums: [1, 2, 3, 4] }, output: 6 },
  { input: { nums: [4, 2, 3, 15] }, output: 5 },
])('input: nums ', ({ input: { nums }, output }) => {
  expect(numberOfGoodSubsets(nums)).toEqual(output)
})