ABC147 D - Xor Sum 4

ABC147 Dを解説ACしました。 覚えたことをメモ書きしていきます。

問題

atcoder.jp

考えたこと

二重ループしたくなる数式だけど、制約的に二重ループだと絶対間に合わない。 XORの和をとっていくので、先に足し合わせてXORとったら行けたりしないかな？と思って小さくやってみたけどだめだった。 このあたりでギブアップ。

解答

XORを考えるときのセオリーに、bitごとに考えるというものがあるらしい。 bitごとに見ていくと、XORをとった結果1となるのは、1 xor 0 のパターンなので、 桁ごとに着目して立っている個数と立っていない個数をかけ合わせると、その桁が最終的にどうなっているかがわかる？

#include <bits/stdc++.h>

using namespace std;

int main() {

    long long n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    long long mod = 1000000007;
    long long two = 1;
    long long ans = 0;

    for(int i = 0; i < 60; i++){
        long long even = 0;
        long long odd = 0;
        for(int j = 0; j < n ; j++){
            if(a[j] & (1LL << i)) odd++;
            else even++;
        }
        ans += (((even * odd) % mod) * (two % mod)) % mod;
        ans = ans % mod;
        two *= 2;
    }

    cout << ans << endl;

    return 0;
}

新しく知ったこと

• XORのセオリーとして、bitごとに考えるとよい。

• 1 << 60とかやるとバグる。long longとして扱ってほしいときはLLってちゃんとつける。

参考にした解説

drken1215.hatenablog.com