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

問題概要 (ARC 092 D / ABC 091 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;
}

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

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

AtCoder ABC 091 D - Two Sequences (ARC 092 D) (黄色, 500 点)

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

制約

解法