題意

題目鏈接

給出\(n\)個數，問任意選幾個數，它們\(\&\)起來等于\(0\)的方案數

Sol

正解居然是容斥原理Orz，然而本蒟蒻完全想不到。。

考慮每一種方案

答案=任意一種方案 - 至少有\(1\)位為\(1\)的方案 + 至少有兩位為\(1\)的方案 - 至少有三位為\(1\)的方案

至少有\(i\)位為\(1\)的方案可以dp算，設\(f[x]\)表示滿足\(f[x] = a_i \& x = x\)的\(a_i\)的個數

最終答案$ = (-1)^{bit(i)} f[i]$

\(f\)數組可以通過高維前綴和預處理

#include<bits/stdc++.h> #define Pair pair<int, int> #define MP make_pair #define fi first #define se second using namespace std; const int MAXN = 3e6 + 10, mod = 1e9 + 7, B = 20; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, a[MAXN], bit[65537], f[MAXN]; int add(int &x, int y) {if(x + y < 0) x = x + y + mod;else x = (x + y >= mod ? x + y - mod : x + y); } int mul(int x, int y) {return 1ll * x * y % mod; } int fp(int a, int p) {int base = 1;while(p) {if(p & 1) base = mul(base, a);a = mul(a, a); p >>= 1;}return base; } int get1(int x) { // return __builtin_popcount(x);return bit[x & 65535] + bit[x >> 16]; } int main() {for(int i = 1; i <= 65536; i++) bit[i] = bit[i >> 1] + (i & 1);N = read();for(int i = 1; i <= N; i++) a[i] = read(), f[a[i]]++;int Lim = (1 << B) - 1, ans = 0;for(int i = 0; i <= 20; i++)for(int sta = 0; sta <= Lim; sta++) if(!(sta & (1 << i))) add(f[sta], f[sta | (1 << i)]);for(int sta = 0; sta <= Lim; sta++) {int k = (get1(sta) & 1) ? -1 : 1;add(ans, mul(k, fp(2, f[sta])));}cout << ans;return 0; }

總結

以上是生活随笔為你收集整理的cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。