けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 092 D - Two Sequences (500 点)

桁ごとに考えるしかなさそうなのはそれはそう...

問題へのリンク

問題概要 (ARC 092 D / ABC 090 D)

 N 要素の数列  a_1, a_2, ..., a_N b_1, b_2, ..., b_N が与えられる。 N^{2} 個の整数  a_i + b_j の XOR 和を求めよ。

制約

  •  1 \le N \le 10^{5}
  •  0 \le a_i, b_i <  2^{28}

解法

XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 N^{2} 個の整数のうち、 k 桁目のビットが立っているやつが何個あるかを数えればよい。

 a_i に対して、 a_i + b_1,  a_i + b_2, ...,  a_i + b_N のうちの何個について、 k 桁目にビットが立っているかを求めることを考える。

ここで

 a_i + b_j k 桁目の値が 1
 a_i + b_j ( {\rm mod}. 2^{k+1}) の値が  2^{k} 以上  2^{k+1} 未満

で、これは  a_{i},  b_{j} に対して  {\rm mod}. 2^{k+1} をあらかじめとっておいたとき、

  •  2^{k} - a_{i} \ge 0 のとき、 2^{k} - a_{i} \le b_{j} <  2^{k+1} - a_{i}
  • そうでないとき、 0 \le b_{j} <  2^{k+1} - a_{i} または  2^{k+1} + 2^{k} - a_{i} \le b_{j} <  2^{k+1}

と同値である。こうして、これを満たす  b_j の個数は予め  b をソートしておいて二分探索などで求めることができる。

全体の計算量は  O(N\log{N}\log{\max(a_i, b_j)})

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> a, b;

int main() {
    cin >> N;
    a.resize(N); for (int i = 0; i < N; ++i) cin >> a[i];
    b.resize(N); for (int i = 0; i < N; ++i) cin >> b[i];
    int res = 0;
    for (int digit = 29; digit >= 0; --digit) {
        int bekihigh = 1<<(digit+1), bekilow = 1<<digit;
        for (int i = 0; i < N; ++i) a[i] %= bekihigh, b[i] %= bekihigh;
        sort(b.begin(), b.end());
        long long num = 0;
        for (int i = 0; i < N; ++i) {
            int add = 0;
            if (bekilow - a[i] >= 0) {
                add += lower_bound(b.begin(), b.end(), bekihigh-a[i])
                        - lower_bound(b.begin(), b.end(), bekilow-a[i]);
                
            }
            else {
                add += lower_bound(b.begin(), b.end(), bekihigh-a[i]) - b.begin();
                add += lower_bound(b.begin(), b.end(), bekihigh)
                        - lower_bound(b.begin(), b.end(), bekihigh + bekilow - a[i]);
            }
            num += add;
        }
        if (num & 1) res += bekilow;
    }
    cout << res << endl;
}