F. A x B Problem

#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;
}