順次追記: 競技プログラミングの知識（XOR編）
Q. これはなに？
考察で要求された知識や考え方を雑多に書くだけのメモ帳、XOR編です。
ちなみに僕が知ってることは省くので、網羅的ではないです。ゆるして。
XORの基本情報
XORは排他的論理和と呼ばれる演算の一種。
真理値表にするとこんな感じになる演算。
| XOR | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
競技プログラミングで使うXORは、ある整数をbit毎に見て上の演算を行うことを指す。
XORの性質
以下では、AtCoderのeditorialにならって をXORの演算子とする
- 可換性
- 結合性
- XORの逆元はXOR
要は偶数回同じ数をXORすると打ち消せる
- 各桁のbitが演算によって繰り上がったりしない（桁あふれしない）
各問題で使えるXOR
ABC126-F XOR Matching
使う考え方
- XORの逆元はXORであること
のXOR,
のXOR,
のXOR, ... , は全て
になる
- 以上の操作で
個の
