题目描述
给一个整数的数组nums，数组中的元素不超过30，数组长度不超过\(10^5\)
给出了好子集的定义（数组中所有元素成绩可以拆分为互不相同质数的积）
对好子集个数的要求是不同子集删除的下标不同，那么也被视为不同的子集
问给定数组nums的好子集的个数？
| f1-状态压缩+动态规划 |
基本分析
- 直观的看，哪些元素不能放到好子集中去？是能整除某个平方数，例如4，8，9
- 进一步细想，能在1-30之间，作为构建子集的质数有哪些？1+10个质数
- 通过以上分析，想到怎么定义dp状态？f[i][state]为考虑范围在[1,30]的前i个数，并且好子集拆解结果用到的质数为state时候的方案数
- 初始状态怎么定义？f[1][0]=1, 表示当只有数值1的话，只有空集是合法的
- 接下来怎么考虑转移？
- 不考虑数字i，对应f[i][s] = f[i-1][s]
- 考虑数字i，这个时候又有情况需要区分
- 数字i可以不能分解为几个不同质数相乘，去换下一个数字i
- 数字i可以分解成几个不同质数相乘（对应为sub）。遍历所有可以转移的前一个状态prev(prev和sub的&是0)来尝试转移
- 对1的情况怎么特殊处理？可以把1的次数当做系数考虑
代码
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
mod = 10**9+7
cnt = Counter(nums)
nmask = 1<<10
# 定义dp状态
# mask取0-nmask-1，i取0-30
f = [[0]*nmask for _ in range(31)]
# 取前1个数字，mask为0的方案个数是1
f[1][0] = 1
for i in range(2, 31):
for mask in range(nmask):
f[i][mask] = f[i-1][mask]
if cnt[i] == 0:
continue
flag = True
cur = 0
for j, p in enumerate(ps):
if i % (p*p) == 0:
flag = False
break
if i % p == 0:
cur |= 1<<j
if not flag:
continue
for prev in range(0, nmask):
if prev & cur != 0:
continue
f[i][prev|cur] = (f[i][prev|cur] + f[i-1][prev]*cnt[i]) % mod
ans = 0
for mask in range(1, nmask):
ans = (ans + f[30][mask]) % mod
for i in range(cnt[1]):
ans = ans * 2 % mod
return ans
复杂度
时间：\(数值范围为30，状态数是1024，dp部分复杂度是O（C \cdot M）\)
空间：\(O(C \cdot M)\)
总结
这个题应该没有完全吃透，后面还要回顾。
怎么把nums和质数数组对应起来？题目给了nums的取值范围是1-30，就是暗示了质数可以取其中的10个，进而哪些质数取不取就可以用二进制的mask表示。
关于枚举每个数和mask的关系，这里有些存疑，为什么要先遍历某个数i，然后遍历所有的mask？从常规定义看是考虑1-30的前i个数，且对应的质数分解为mask时的方案总数，从这个角度看也许解释的通
某个数的质数分解方面：这里的代码写的复杂了，更好的写法是试除法
赋值问题：不管这个i是不是能分解成质数，需要先把不考虑i的情况转移过来f[i][s] = f[i-1][s]
转移写法：这里是枚举之前值prev，保证prev和cur不重
边界问题：统计最终结果的时候，不能把mask=0考虑进去，但是在dp之前，必须给出f[1][0]=1的边界，这个怎么理解？
系数问题：对所有合法的结果，可以考虑cnt[1]个位置的1取或者不取都有2种可能，对应的系数是\(2^{cnt[1]}\)