CodeChef September Challenge 2020 - Find XOR

• 問題
• AC

仮に$K=0$を尋ねることが可能だとすると、$K=0$による総和と$K=2^e$による総和の差は$(A_i)$の中で第$e$ビットが$1$であるものの総数-第$e$ビットが$0$であるものの総数に等しい。これを利用すると各桁の立っているビットの数がわかるので、偶数ならXORを0、奇数なら1とすればよい。

実際には$K\ge1$という制約があるが、代わりに全ビットを反転したもの（=$2^{20}-1$とXORを取ったもの）を$K$とすれば同じことができる。

また、素朴にやると$K=0, 2^0, 2^1, ..., 2^{19}$を全部尋ねる必要があってクエリの回数が21回になってしまう。$K=2^0, ..., 2^{18}$を調べて$K=0$の場合の生の総和と比較することで、$K=2^{19}$は省略できて20回になる。

---

$N \le 10^3 < 2^{10}$だから、11ビットくらいで区切れば2つの質問を1つのクエリでできそうと思ったが、分離がかなり複雑になりそうなので方針を変えた。