Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Codeforces Round #257 (Div. 1) D. Jzzhu and Numbers
// Codeforces Round #257 (Div. 1) D. Jzzhu and Numbers
// http://codeforces.com/problemset/problem/449/D
//
// 包除原理
// やりたいのは and して *11*1*11*1 みたいなパターンになる数を求めること。
// 0110101101 を部分集合として持つ a[i] の個数が分かればいい。
// →bitDP(高速ゼータ変換)
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long modpow(long long a, long long b, long long mod) {
long long result = 1;
for (; b > 0; a = a * a % mod, b /= 2) if (b & 1) result = result * a % mod;
return result;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
vector<long long> dp(1 << 20);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
dp[a[i]]++;
}
for (int j = 0; j < 20; j++) {
for (int i = 0; i < 1 << 20; i++) {
if (~i & 1 << j) {
(dp[i] += dp[i | 1 << j]) %= mod;
}
}
}
long long ans = 0;
for (int i = 0; i < 1 << 20; i++) {
if (__builtin_parity(i) == 0) {
(ans += modpow(2, dp[i], mod)) %= mod;
} else {
(ans += mod - modpow(2, dp[i], mod)) %= mod;
}
}
cout << ans << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment