はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるXOR問題まとめ

XOR

  • 排他的論理和
  • 性質1「交換則、結合則が成り立つ」2「a xor a = 0」3「ある数xのb番目のビットが1である <=> x mod 2^(b+1) ≧ 2^b」
  • 方針1「xor計算は各ビットで独立なので別々に計算」2「trieを使ったxorの最大最小探索がある」
  • 無向グラフを任意回移動してxorを取って回る -> サイクル基底を使うかも
  • 2ビットのXOR+ShiftはGCDに帰着できるかも 解説