Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using i64 = long long;
- #define int i64
- using u64 = unsigned long long;
- using i128 = __int128;
- int safe_lg(int x) { return (x == 0 ? -1 : __lg(x)); }
- int32_t main() {
- cin.tie(0)->sync_with_stdio(0);
- int N; cin >> N;
- int lgmx = 0;
- vector<u64> A(N);
- for (auto &x : A) cin >> x, lgmx = max(lgmx, safe_lg(x) + 1);
- vector<u64> revA = A;
- for (auto &x : revA) {
- x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);
- x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
- x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
- x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8);
- x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
- x = ((x >> 32) & 0x00000000FFFFFFFF) | ((x & 0x00000000FFFFFFFF) << 32);
- }
- auto fwt_and = [&](auto &a, int n, int op) {
- for (int L = 2; L <= n; L <<= 1) {
- for (int i = 0; i < n; i += L) for (int j = 0; j < L/2; ++j) {
- a[i+j] = (a[i+j] + a[i+j+L/2] * op);
- }
- }
- };
- u64 U = (u64(1) << lgmx) - 1;
- vector<i64> X(U + 1, 0);
- vector<i128> Y(U + 1, 0);
- for (auto x : A) ++X[x];
- for (int b = 0; b <= 2*lgmx-2; ++b) {
- u64 u = (u64(1) << min(b+1, lgmx)) - 1;
- for (auto x : revA) Y[(x >> (63-b)) & u] += i128(1) << b;
- }
- fwt_and(X, U+1, 1);
- fwt_and(Y, U+1, 1);
- for (u64 i = 0; i <= U; ++i) Y[i] *= X[i];
- fwt_and(Y, U+1, -1);
- for (int b = 0; b <= 2*lgmx-2; ++b) {
- u64 u = (u64(1) << min(b+1, lgmx)) - 1;
- for (int i = 0; i < N; ++i) Y[A[i] & (revA[i] >> (63-b)) & u] -= i128(1) << b;
- }
- i128 ans = 0;
- for (u64 i = 0; i <= U; ++i) { if (popcount(i) & 1) ans += Y[i]; }
- ans /= 2;
- string ans_str;
- do ans_str += char(ans % 10 + '0'), ans /= 10; while (ans);
- reverse(begin(ans_str), end(ans_str));
- cout << ans_str << "\n";
- return 0;
- }
Add Comment
Please, Sign In to add comment
