AtCoder Beginner Contest 091 ABC091 D - Two Sequences

AtCoder Beginner Contest 091 ABC091 D - Two Sequences

問題概要

長さNの二つの数列a,bがある。これらの全ての組み合わせa_i + b_jに対して、全てxorをとったときの値を求めよ。

解説

方針

xorなので、桁ごとに考えることができる。ある桁kが1となるのは、その桁のbitが立っている個数が奇数のときである。

解答方法

ここで、k桁目を考えるとき、それより上の桁は無視できるので、mod 2^k+1を取っておくと見通しがよい。あるaを固定して考える。aと足して、k桁目が1となる条件は、2^k <= a + b < 2^(k+1) or 2^(k + 1) + 2(k) <= a + b < 2(k + 2)である。aを固定し、bがこれを満たす個数を数えればよいから、二分探索で可能。

提出

int main() {

    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin>>a[i];
    vector<ll> b(N);
    rep(i,N)cin>>b[i];
    ll ans = 0;
    rep(k, 30){
        ll T = bit(k);
        vector<ll> amod(N);
        vector<ll> bmod(N);
        rep(i,N){
            amod[i] = a[i] % (2 * T);
            bmod[i] = b[i] % (2 * T);
        }
        sort(all(bmod));
        ll sum = 0;
        rep(i,N){
            // T <= a + b < 2T
            sum += lower_bound(all(bmod), 2 * T - amod[i]) - lower_bound(all(bmod), T - amod[i]);
            // 3T <= a + b < 4T
            sum += lower_bound(all(bmod), 4 * T - amod[i]) - lower_bound(all(bmod), 3 * T - amod[i]);
        }
        if(sum % 2 == 1)ans += T;
    }
    cout << ans << endl;
}