問題リンク
https://atcoder.jp/contests/arc092/tasks/arc092_b
方針
XORなので桁ごとにいくつの項のbitが立っているか考える(典型)。
和を取ると繰り上がりが発生することの解釈
ある桁d(下から)考えているとき、それより上の桁の和の結果はその桁のbitに影響を及ぼさないので、
(d桁目で繰り上がったかどうか、まではd桁目の結果に影響を及ぼすが、繰り上がった桁が更に繰り上がったかどうかはd桁目に影響を及ぼさない) d+1桁目以降の情報を切り捨ててから和を取ることを考えてもd桁目の答えは変わらない。
aを固定すると、d桁目に1が立つ値は、値の昇順に区間になっているので、二分探索で範囲を取れる。
- aaa
- 22
