ARC092 D. Two Sequences - phyllo’s algorithm note

問題

長さがNの非負整数列が2つ与えられ、それぞれA,Bとする。
1<=i,j<=Nとして、A,Bそれぞれの要素の和(a_i + b_j)がN^2個作れる。
このN^2個の数字のxorを計算せよ。

制約

1 <= N <= 2 * 10^5
0 <= a_i, b_j < 2^28

解法

単純に計算しようとするとN^2 = (4 * 10^10)個のxorを計算するので間に合わない。(頑張れば間に合う？)
整数のxorはビットごとに計算されるので、各ビットごとに分けて計算できるか考える。

想定解

今、答えのiビット目を求めることを考える。
xorの性質として、「ある整数xのb番目のビットが1である」というのは「x mod 2^(b+1)が2^b以上」というので判断できることを使う。
競技プログラミングにおけるXOR問題まとめ - はまやんはまやんはまやん

この性質を使うと、(a_i + b_j)はmodを取って、「(a_i + b_j) mod 2^(i+1)」が「2^i」以上かどうかで判断できる。
「a_i mod 2^(i+1)」と「b_j mod 2^(i+1)」をしておけば、その和は0から4 * 2^i未満に収まり、和のiビット目の判断は、

0以上2^i未満：0
2^i以上2 * 2^i未満：1
2 * 2^i以上3 * 2^i未満：0
3 * 2^i以上4 * 2^i未満：1

の4つのうちのどれかになる。

すべての要素をmod 2^(i+1)しておいたAとBの要素同士の和で、それぞれの範囲にどれだけの個数があるか？が高速に求められればよい。
これには、modを取った配列をA'、B'とすると、どちらもソートしておくと、A'の各要素a'_iについて、和がX以上になる要素数を二分探索で求める、などすればO(NlogN)で求められる。
Xとしては、2^i、2 * 2^i、3 * 2^iがわかれば、↑の4パターンにおける個数がわかるので、1となる部分の個数がわかると、それが奇数かどうかで答えのiビット目が1か0かがわかる。

結局、ビットは30ぐらいなので、O(30 * NlogN)程度で求められた。

別解

本番は、ちょっと違う方法で通した。

まずは最下位ビットから考える。
配列Aの要素のiビット目が1の数をA1、0の数をA0とし、同様に配列BについてもB1、B0とする。
すると、A1 * B1は桁上りは発生して0になるので、各要素和のiビット目が1になっている個数は「A0*B1 + A1*B0」になる。

続けて一つ上のビットについて考える。
一つ下のビットでA1*B1個の桁上りが発生しているので、1になっている個数は「一つ前のビットでのA1*B1 + A0*B1 + A1*B0」で求められる。

ここで、入力例1などで試していると、問題があることがわかる。
例えば、2進数表記でa_i=011とb_j=001のようなものがあった場合、最下位ビットでの桁上りがその二つ上のビットまで影響する。
しかし、上記のような求め方をしようとすると、一つ前のビットでA1*B1個の桁上りがあるが、どの要素の和のところで桁上りがあったかがわからなくなるので、前のビットの影響を受けての次の桁上りが何個あるのかを求められない。

ただ、上記の流れから、答えのiビット目が0か1かは「(i-1)桁からの桁上りしてくる個数 + A0*B1 + A1*B0」が奇数か偶数かで求められることはわかる。
そこで、この「桁上りしてくる個数」が求められないかを考える。

今、iビット目を考える。
桁上りが何個あるかを考えると、結局、配列の各要素のiビット未満の部分が必要であることがわかる。
具体的には「配列A,Bの各要素のiビット未満の部分について注目し、その部分の和が2^i以上になる個数」を求めれば桁上りの個数が求められることがわかる。

各配列要素のiビット未満の部分だけにした配列A'、B'を計算するのにO(N)。
A'、B'をソートするのにO(NlogN)。
A'とB'の要素の和が2^i以上になる個数を求めるのは、A'を大きい方から、B'を小さい方から尺取り的に、

int j = 0;
for(int i=A'.size(); i>=0; i--){
  while(j<B'.size() && A'[i]+B'[j]<2のi乗) j++;
  個数 += B'.size() - j;
}

のように求めるか、想定解と同じ二分探索で求めてあげればよい。

結局、桁上りの個数がこのようにO(NlogN)で求められたので、各桁について「桁上りの個数 + A0*B1 + A1*B0」を求めていけば答えが求まる。