• $2n \mathbin{\oplus} (2n + 1) = 1$
• $4n \mathbin{\oplus} (4n+1) \mathbin{\oplus} (4n+2) \mathbin{\oplus} (4n+3) = 0$
  • 証明1 (bitごとに考える)
    • $4n, 4n+1, 4n+2, 4n+3$ の（2進数の）1桁目と2桁目は $0 \mathbin{\oplus} 1 \mathbin{\oplus} 2 \mathbin{\oplus} 3 = 0$ となる
    • （2進数の）3桁目以降はすべて一致しているので打ち消して 0 になる。
  • 証明2
    • $4n \mathbin{\oplus} (4n+1) = 1$、$(4n+2) \mathbin{\oplus} (4n+3) = 1$ から従う
  • 同様に $(4n-2) \mathbin{\oplus} (4n-1) \mathbin{\oplus} 4n \mathbin{\oplus} (4n+1) = 0$ も成り立つ
  • $(4n-1) \mathbin{\oplus} 4n \mathbin{\oplus} (4n+1) \mathbin{\oplus} (4n+2) = 0$ は成り立たない
• $x \mathbin{\oplus} x = 0$
  • 特に偶数個は打ち消しあう。奇数個の場合は1個残る。
  • 出題例: ARC168 B - Arbitrary Nim
  • 参考: Zobrist Hash (ハッシュ)
• $x \mathbin{\oplus} y = x \mathbin{\oplus} z$ ならば $y = z$
  • 不偏ゲーム でこの対偶「y ≠ z ならば x ⊕ y ≠ x ⊕ z」がよく出てくる (xor sum が変化するという話に使える。)
  • 証明: 両辺に x を xor として加えれば良い。
  • 一般にアーベル群の性質は成り立つ。
• $0 \oplus 2^n-1 = 1 \oplus 2^n -2 =2 \oplus 2^n-3 =\cdots = 2^n-1$
  • 補数と関係ある？
• $a \oplus b = \operatorname{mex}(\{ a' \oplus b \mid 0 \leq a' < a\} \cup \{ a \oplus b' \mid 0 \leq b' < b\} )$
  • 参考: Sprague Grundy Theorem, Nimber
• x が a か b のとき、x^a^b で x が a のとき b、b のとき a が取得できる
  • ABC420 E 解説: https://atcoder.jp/contests/abc420/editorial/13740

https://atcoder.jp/contests/abc236/tasks/abc236_b