CF449D Jzzhu and Numbers题解
Fat_Fish
·
·
题解
令 AND 表示若干个数 & 起来的结果。
令 x 被 y 包含表示 x & y == y
直接设状态不好做。
于是转变思路。
令 h_i 表示 AND 被 i 包含的所有 AND 的方案数。
则答案可以由 h_i 容斥得到。
由于只关心 h_i 中 i 在二进制下有几个 1 ，所以简化成代码中的 g_i , 表示有 i 个 1 。
问题转化成如何求 h_i 。 事实上只需求出 f_i , 表示有多少个 a_x 被 i 包含。
$f_i$ 显然可以 $SOSdp$ 求得。
代码如下 :
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 20) + 100;
const int Mod = 1e9 + 7;
int n, res, a[N], f[N], g[N], _2[N];
inline void upd(int &x, int y) {
x += y;
if(x >= Mod) x -= Mod;
if(x < 0) x += Mod;
return;
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
_2[0] = 1;
for(int i = 1; i < (1 << 20); ++i) _2[i] = _2[i - 1] * 2 % Mod;
for(int i = 1; i <= n; ++i) cin >> a[i], ++f[a[i]];
for(int j = 0; j < 20; ++j)
for(int i = (1 << 20) - 1; ~i; --i)
if(i >> j & 1) upd(f[i ^ (1 << j)], f[i]);
for(int i = 0; i < (1 << 20); ++i) upd(g[__builtin_popcount(i)], _2[f[i]] - 1);
for(int i = 0; i < 20; ++i) {
if(i & 1) upd(res, -g[i]);
else upd(res, g[i]);
}
cout << res << '\n';
return 0;
}
```