题目
思路
- 类似01背包优化的状态压缩dp（误）
- 首先按照数字分出是否有平方子集，然后再计数cnt[x]
- 枚举合法的数字（2 ~ 30），为什么不算1？因为所有的1都有两种状态，选或者不选（或者说他不算是质数），直接在最后的结果上2cnt[1]2^{cnt[1]}2cnt[1]即可
- 枚举所有状态（0 ~ 1 << 10, 倒着来是类似01背包的优化），如果和当前状态mask互不相交，递推至mask|j
- 最后无平方子集的数量就是(∑0210f)∗2cnt[1]−1(\sum_0^{2^{10}}f) * 2^{cnt[1]} - 1(∑0210f)∗2cnt[1]−1
代码
ini
复制代码
const int mod = 1e9 + 7; int sum[31]; int p[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; typedef long long LL; LL f[(1 << 11) + 10]; class Solution { public: int squareFreeSubsets(vector<int> &nums) { for (int i = 2; i <= 30; i++) { for (int j = 0; j < 10; j++) { if (i % p[j] == 0) { if (i % (p[j] * p[j]) == 0) { sum[i] = -1; break; } sum[i] = sum[i] | (1 << j); } } } map<int,int>cnt; for(int i = 0;i < nums.size();i++) cnt[nums[i]]++; int v = 1 << 10; memset(f,0,sizeof f); f[0] = 1; for(auto it : cnt) { int a = it.first; int b = it.second; int mask = sum[a]; if(mask > 0) { for(int i = v;i >= 0;i--) { if((i & mask) == 0) { f[i | mask] = (f[i] * b + f[i | mask]) % mod; } } } } LL ans = 0; int x = cnt[1]; int y = 1; while(x) { y = y * 2 % mod; x--; } for(int i = 0;i < 1 << 10;i++) { ans = (f[i] + ans) % mod; } ans = (ans * y) % mod; return (ans+ mod - 1) % mod; } };
