上个月提离职，领导头都没抬就批了(单休月薪5000)，今天突然在微信上问我“后悔了没”，想回来也可以，不过薪酬要重新定!

网友上个月提离职，原公司那领导挺潇洒，头都不抬一下就批了。关键那工作也不是什么香饽饽，单休，一个月五千，打工人听了都得沉默两秒。

结果人家走了以后，在珠海找了个双休的，底薪八千，五险一金也安排上了。领导这时候突然微信来一句，问人家后不后悔，还说想回去也不是不行，但工资得重新谈。

这话就很有意思。之前不当回事，觉得员工离了公司不行。现在发现人真走了，日子还过得更顺了，才开始装淡定。

最扎心的是，人家确实后悔了。

后悔的不是离职，是怎么没早点跑。估计领导看到现状那一刻，手机都拿不稳了。

这题别上来就回溯，肯定难受

「好子集的数目」这题，第一眼很容易往回溯上想：选、不选、算乘积、判断是不是好子集。

这个方向我一般第一眼就不太信。

因为 nums.length 可以比较大，真按子集枚举，跑着跑着就没了。这里真正该盯的不是数组长度，而是 nums[i] 的范围：只在 1 ~ 30。

这个范围太小了，小到可以直接把每个数字拆成质因子状态。

题目里的“好子集”，要求乘积能拆成若干个互不重复的质数相乘。

比如：

6 = 2 * 3      可以
10 = 2 * 5     可以
12 = 2 * 2 * 3 不行

所以像 4、8、9、12、16、18、20、24、25、27、28 这种数字，里面已经带了重复质因子，根本不能进好子集。

剩下能用的数字，都可以压成一个二进制状态。

1 ~ 30 里面涉及的质数只有这些：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

用 10 个 bit 就能表示一个数字用了哪些质数。

比如：

6  -> 2 * 3 -> 0000000011
10 -> 2 * 5 -> 0000000101

如果两个数字的 mask 有交集，说明质因子重复，不能放在同一个子集里。

这里用动态规划更稳。

dp[mask] 表示：当前已经选出的质因子集合是 mask 时，有多少种选法。

代码我会这么写：

classSolution:
defnumberOfGoodSubsets(self, nums):
        mod = 10 ** 9 + 7

        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

        cnt = [0] * 31
for x in nums:
            cnt[x] += 1

defmake_mask(x):
            mask = 0

for i, p in enumerate(primes):
if x % (p * p) == 0:
return-1

if x % p == 0:
                    mask |= 1 << i

return mask

        dp = [0] * (1 << len(primes))
        dp[0] = 1

for x in range(2, 31):
if cnt[x] == 0:
continue

            mask = make_mask(x)
if mask == -1:
continue

for old in range(len(dp) - 1, -1, -1):
if old & mask:
continue

                new_mask = old | mask
                dp[new_mask] = (dp[new_mask] + dp[old] * cnt[x]) % mod

        ans = sum(dp[1:]) % mod

if cnt[1]:
            ans = ans * pow(2, cnt[1], mod) % mod

return ans

这里有个地方容易写错，就是 cnt[x]。

假设数组里有 3 个 6，你不能同时选两个 6，因为质因子 2 和 3 会重复。

但你可以从这 3 个 6 里面任选一个，所以贡献是 cnt[6]，不是 2^cnt[6]。

1 又是另一回事。

1 不提供任何质因子，放不放都不影响“好不好”。所以每一个已经成立的好子集，都可以随便搭配这些 1。

有 k 个 1，就乘上：

2 ** k

因为每个 1 都有选和不选两种情况。

这题卡的不是代码长度，而是别把数字当成普通数组去枚举。范围只有 30，就该往计数、状态压缩上想。

数组长度大，不一定难。

值域小，往往就是突破口。