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

hamayanhamayan's blog

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

XOR

  • 排他的論理和
  • 性質1「交換則、結合則が成り立つ」2「a xor a = 0」3「ある数xのb番目のビットが1である <=> x mod 2^(b+1) ≧ 2^b」性質4「0≦aのとき、4a, 4a+1, 4a+2, 4a+3のxor和は0」
  • 方針1「xor計算は各ビットで独立なので別々に計算」2「trieを使ったxorの最大最小探索がある解説
  • 数列の各数をビット毎に分解して行列と考えて、ガウスの消去法を行うことで正規化する問題がある
    • 問題
    • 任意要素の入れ替えができる、隣り合う要素でなくてもXORできる→行基本変形ができる
    • この場合に行標準形に変形して、正規化できるみたい。これはガウスの消去法などで求まる
    • ガウスの消去法の結果として、行列のランクRも求めることができる
      • すると解の個数は2^(自由度) = 2^(N-R)となるが、これはsubsetでxorすることで作ることのできる数の個数に対応している。
      • けんちょんさんの記事が最強
  • 無向グラフを任意回移動してxorを取って回る -> サイクル基底を使うかも
  • 2ビットのXOR+ShiftはGCDに帰着できるかも 解説 類題
  • パスの辺全てにXORを取るのは、頂点について繋がっている辺のコストのXORを取ったA[i]を用意した時に、端点A[s]とA[t]のみにXORを取るのと同じ これ