ARC092-D Two Sequences (500)
検索用
ビットごと 二分探索
概要
N(最大20万)長の、要素ごとが2^28まである二つの数列a, bについて、以下のansを求めよ。
ll ans = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
ans ^= (a[i] + b[j]);
}
}
cout << ans << endl;
ACするまで
1.どうせbitごとに見るんだろうなと予想
2.見てる桁が0-idxで下からk桁目の時、
a_i + b_ j (mod 2^(k+1)) で 2^k より大きければ、その桁のbitは立つ。最終的にそれの数を合計して、XORするので奇数個あったら答えの部分のk bit目は立つ。
3.つまり2^kが立つような組み合わせを爆速で数えたいなぁ
2.見てる桁が0-idxで下からk桁目の時、
a_i + b_ j (mod 2^(k+1)) で 2^k より大きければ、その桁のbitは立つ。最終的にそれの数を合計して、XORするので奇数個あったら答えの部分のk bit目は立つ。
3.つまり2^kが立つような組み合わせを爆速で数えたいなぁ
4.実は2の式をもっと詰めるときれいに1になる区間と0になる区間がわかる。
5. 4のこれの境界がわかれば個数が分かる。->二分探索
5. 4のこれの境界がわかれば個数が分かる。->二分探索
考察
この問題で、kビット目について考えるとき、ひとまずaもbもmod 2^(k+1)で考える。なぜならば、それより上の桁はkビット目のXORの結果に影響しないからである。
ここを詰め切れなかったのだが、aとbの和の大小関係によって、bitが立つかどうか、次の式のようになる。
- [0, 2^k) 2^kの位に届かないので、立たない。
- [2^k, 2 * 2^k) 2^(k+1)の位には届かないので、2^kの位は立つ。
- [2 * 2^k, 3 * 2^k) 2^(k+1)の位が立つので、2^kの位がいったん0になる。よって立たない。
- [3 * 2^k, 4 * 2^k) 2^(k+1)の位が立つうえで、2^kの位もたつ。よって立つ。
このようにa+bのkビット目が立つか立たないかはどの連続した区間に属するかに依る。区間の境界は二分探索！と相場は大体決まってる。
あとは事前にaとbのmod 2^(k+1)を事前計算して、aを決めた時に境界となる値をb内で二分探索して、個数を数え上げればいい。区間の定義が半開区間なので、lower_bound()同士のイテレータの差で個数が分かる。
