Xor Sum 4 [AtCoder Beginner Contest 147 D]

https://atcoder.jp/contests/abc147/tasks/abc147_d

解説

https://atcoder.jp/contests/abc147/submissions/8892568

XORの計算は桁毎に考えることができる。
そのため、桁ごとに総和を求めて、その総和を取ることで答えとしよう。
こうすると、1がone個、0がzero個あるという風に問題をより簡単にすることができる。
この中で、XORを取って、1になる組み合わせはzeroone通りであるため、総和もzeroone*2^桁目となる。
これを全ての桁に対してとる。

mintはいらないんだけど、これを使わないと安心できないからだになっているので、一応使っておく。

int N; ll A[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    mint ans = 0;
    rep(b, 0, 60) {
        ll msk = 1LL << b;

        int zero = 0, one = 0;
        rep(i, 0, N) {
            if (A[i] & msk) one++;
            else zero++;
        }

        ans += mint(msk) * zero * one;
    }
    cout << ans << endl;
}