D - Jzzhu and Numbers https://codeforces.com/contest/449/problem/D
这个容斥没想出来... 我好菜啊..
f[ S ] 表示若干个数 & 的值 & S == S 得 方案数, 然后用这个去容斥.
求 f[ S ] 需要用 SOSdp
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define PLL pair<LL, LL>
- #define PLI pair<LL, int>
- #define PII pair<int, int>
- #define SZ(x) ((int)x.size())
- #define ull unsigned long long
- using namespace std;
- const int N = 1e6 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = 1e9 + 7;
- const double eps = 1e-8;
- int cnt[1<<20], bin[N], num[1<<20], n;
- int main() {
- for(int i = bin[0] = 1; i <N; i++) bin[i] = bin[i - 1] * 2 % mod;
- scanf("%d", &n);
- for(int i = 1; i <= n; i++) {
- int x; scanf("%d", &x);
- cnt[x]++;
- }
- for(int i = 0; i < 20; i++)
- for(int S = 0; S < (1 << 20); S++)
- if(S>> i & 1) cnt[S ^ (1 << i)] += cnt[S];
- LL ans = bin[n];
- for(int S = 1; S < (1 << 20); S++) {
- num[S] = num[S-(S&-S)] + 1;
- if(num[S] & 1) ans = (ans - bin[cnt[S]] + mod) % mod;
- else ans = (ans + bin[cnt[S]]) % mod;
- }
- printf("%lld\n", ans);
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2947451.html