AtCoder Regular Contest 092 D - Two Sequences

atcoder.jp

数列 $a_i, b_i (1 \le i \le n)$ が与えられるので、 $a_i + b_j (1 \le i, j \le n)$ のすべてのxorを求めよという問題。 $O(n^2)$ 解法は愚直にやればよいので、 $O(n \log{n})$ 程度の解法を求める必要がある。

xorの値を求める問題はbitごとに独立して行うというのが鉄則。そこで下位bitから求めていこう。最下位ビットは $a_i, b_i (1 \le i \le n)$ の偶奇で4パターンに分かれるが、そのうち2パターンの数が奇数なら1、偶数なら0になることがわかる。上位bitも同じようにやりたいが、足し算なので繰り上がりが発生する。一般にxorの問題は足し算と組み合わせた瞬間難易度が跳ね上がる。

そこで $a_i, b_i \mod 2^k (k=1,2,...,28)$ を順次考えていく。これは直感的にいうと上位ビットを徐々に0に落としていくイメージである。するとk bit目が1になる条件は $(a_i \mod 2^k) + (b_j \mod 2^k)$ の上位ビットが11または01であればよいため、例えば $b_i \mod 2^k$ をソートしておくことで、 $a_i$ を固定すれば二分探索で組み合わせのパターンを探すことが可能になる。具体的には $2^{k-1} - (a_i \mod 2^k) \le b_j \le 2^k - (a_i \mod 2^k) - 1$ 及び $(2^k + 2^{k-1}) - (a_i \mod 2^k) \le b_j$ をカウントすればよい。