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

上个月人家提离职，领导当时连眼皮都懒得抬，批得那叫一个痛快。毕竟单休，一个月五千，估计在领导眼里，你爱走不走，外面人多的是。

结果过了一个月，微信突然来了句：后悔没？想回来也行，不过工资得重新谈。

尴尬的是，人家现在在珠海，双休，底薪八千，五险一金正常交。你说领导看到这消息，脸不绿才怪。

打工人最怕的不是离职，是一直以为自己只能值那点钱。出了门才发现，不是外面没机会，是原来那地方太会压价了。

这后悔是真后悔，后悔没早点跑路。

nums 里一堆 1、2、3、4、8、12 混在一起，这题最容易写歪的地方不是背包，而是把“不好”的数也塞进去了。

好子集要求乘积能拆成互不重复的质数。翻译成代码就是：一个数里不能有平方因子。比如 4 带着 2 * 2，直接扔；8、9、12、16、18 这些也别犹豫，进来只会污染状态。

30 以内的质数就 10 个：

int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

我一般会先把每个数字转成一个 bit mask。第 i 位为 1，表示用了第 i 个质数。比如 6 = 2 * 3，对应 mask 里 2 和 3 两位亮着。

这里有个小坑：判断平方因子时，不能只看能不能整除质数，要看除了一次之后还会不会再整除。

privateintbuildMask(int x, int[] primes){
int mask = 0;
for (int i = 0; i < primes.length; i++) {
int p = primes[i];
if (x % p != 0) {
continue;
        }
        x /= p;
if (x % p == 0) {
return -1;
        }
        mask |= 1 << i;
    }
return mask;
}

接下来就是状态压缩 DP。

dp[mask] 表示当前已经用了这些质数时，有多少种选法。 遍历 2 到 30，每个数字如果出现了 cnt[x] 次，并且它本身合法，就尝试放进已有状态里。

注意同一个值最多选一个。比如有 3 个数字 6，可以选其中任意一个，所以贡献是乘 cnt[6]，不是把 6 重复转移 3 次。重复转移就会把两个 6 同时选进去，乘积里 2 和 3 都重复了，直接错。

完整代码我会这么写：

classSolution{
privatestaticfinalint MOD = 1_000_000_007;
privatestaticfinalint[] PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

publicintnumberOfGoodSubsets(int[] nums){
int[] cnt = newint[31];
for (int v : nums) {
            cnt[v]++;
        }

long[] dp = newlong[1 << PRIMES.length];
        dp[0] = 1;

for (int x = 2; x <= 30; x++) {
if (cnt[x] == 0) {
continue;
            }

int m = buildMask(x);
if (m < 0) {
continue;
            }

for (int used = dp.length - 1; used >= 0; used--) {
if (dp[used] == 0) {
continue;
                }
if ((used & m) != 0) {
continue;
                }

int next = used | m;
                dp[next] = (dp[next] + dp[used] * cnt[x]) % MOD;
            }
        }

long ans = 0;
for (int mask = 1; mask < dp.length; mask++) {
            ans = (ans + dp[mask]) % MOD;
        }

for (int i = 0; i < cnt[1]; i++) {
            ans = ans * 2 % MOD;
        }

return (int) ans;
    }

privateintbuildMask(int x){
int mask = 0;
for (int i = 0; i < PRIMES.length; i++) {
int p = PRIMES[i];
if (x % p != 0) {
continue;
            }

            x /= p;
if (x % p == 0) {
return -1;
            }

            mask |= 1 << i;
        }
return mask;
    }
}

最后单独处理 1。 1 不贡献任何质因子，但它可以跟任意好子集搭配。假设有 k 个 1，每个 1 都有选和不选两种情况，所以答案乘上 2^k。

这题看着像普通子集计数，实际卡点就两个：平方因子要提前过滤，重复数字只能按“选其中一个”来乘次数。把这两处守住，剩下就是 1024 个 mask 滚一遍。