题目链接：1994. 好子集的数目
动态规划。
执行用时：152 ms, 在所有 Python3 提交中击败了100.00%的用户时间复杂度超越了 100% 的用户。
MASK[i] 表示 i 的质因子的组成成分，MASK[i]=gen_mask_for(i)。当 MASK[i] & MASK[j] != 0 时，i 和 j 不属于同一个好子集。
def gen_mask_for(num: int):
factors, state = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], 0
for i, factor in enumerate(factors):
if num % factor == 0:
state |= (1 << i)
return state
VALID[i] 表示 i 是否有重复的质因子，如果有的话，那 VALID[i]=False，VALID[i]=is_valid(i)。VALID[i] is False 时，i 不属于任何一个好子集。
def is_valid(num: int):
for i in range(2, num):
if num % (i * i) == 0:
return False
return True
nums 的好子集有三种：
- 不包含
nums[-1]的子数组的好子集； - 除
nums[-1]外，还包含其它数的好子集； - 仅包含
nums[-1]的好子集。
from collections import Counter
from typing import List
class Solution:
MASK = {1: 0, 2: 1, 3: 2, 4: 1, 5: 4, 6: 3, 7: 8, 8: 1, 9: 2, 10: 5, 11: 16, 12: 3, 13: 32, 14: 9, 15: 6, 16: 1,
17: 64, 18: 3, 19: 128, 20: 5, 21: 10, 22: 17, 23: 256, 24: 3, 25: 4, 26: 33, 27: 2, 28: 9, 29: 512, 30: 7}
VALID = {1: False, 2: True, 3: True, 4: False, 5: True, 6: True, 7: True, 8: False, 9: False, 10: True, 11: True,
12: False, 13: True, 14: True, 15: True, 16: False, 17: True, 18: False, 19: True, 20: False, 21: True,
22: True, 23: True, 24: False, 25: False, 26: True, 27: False, 28: False, 29: True, 30: True}
MOD = 10 ** 9 + 7
def __init__(self):
self.cache = dict()
def number_of_good_subsets(self, nums: List[int], nums_counter) -> int:
if tuple(nums) in self.cache:
return self.cache.get(tuple(nums))
if len(nums) == 0:
res = 0
elif len(nums) == 1:
res = nums_counter.get(nums[0])
else:
cnt1 = self.number_of_good_subsets(nums[:-1], nums_counter) % self.MOD
cnt2 = self.number_of_good_subsets(
list(filter(lambda v: self.MASK[nums[-1]] & self.MASK[v] == 0, nums[:-1])),
nums_counter) * nums_counter.get(nums[-1], 0) % self.MOD
cnt3 = nums_counter.get(nums[-1]) % self.MOD
res = (cnt1 + cnt2 + cnt3) % self.MOD
self.cache[tuple(nums)] = res
return res
def numberOfGoodSubsets(self, nums: List[int]) -> int:
nc = Counter(nums)
count1 = nc.pop(1, 0)
cnt = self.number_of_good_subsets(sorted(filter(lambda k: self.VALID[k], nc.keys())), nc)
return cnt * (2 ** count1) % self.MOD