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

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できる→行基本変形ができる
    • この場合に行標準形に変形して、正規化できるみたい。これはガウスの消去法などで求まる
  • 無向グラフを任意回移動してxorを取って回る -> サイクル基底を使うかも
  • 2ビットのXOR+ShiftはGCDに帰着できるかも 解説
  • パスの辺全てにXORを取るのは、頂点について繋がっている辺のコストのXORを取ったA[i]を用意した時に、端点A[s]とA[t]のみにXORを取るのと同じ これ