tablog

XOR に関連した問題

XOR が問題名に入った問題はたくさんある。

XOR の性質

$x \oplus y = y \oplus x$
$(x \oplus y)\oplus z = x \oplus (y \oplus z)$
$x \oplus 0 = x$
$x \oplus x = 0$

この性質から次の性質が成り立ちます．

数列全体に対してある値で XOR をとっても階差は変化しない $(A_i \oplus x) \oplus (A_{i+1} \oplus x) = A_i \oplus A_{i+1}$

他にも，以下のような性質があります

$(2x)\oplus(2x+1) = 1$
$(2x)\oplus(2y) = 2(x\oplus y)$

足し算は XOR と AND を用いると次のように表せます

$x+y = 2(x \And y) + x \oplus y$

よくあるパターン

bit ごとに見る
求めたい値が bit ごとに求められる場合使える
0/1 の個数を数えたり，桁 dp をしたり
binary-trie*1 *2 を使う
数の大小が大事なときに使う？
数の追加削除，全体に XOR ，K 番目に小さい/大きい，x より大きい要素の数，とかができる
自分自身と XOR を取ると 0 になる性質に注目する
$F_2$ 線形代数
集合を扱うときに使える？

問題

bit ごとに見る

binary-trie を使う

自分自身と XOR を取ると 0 になる性質に注目する

$F_2$ 線形代数

未分類

みんなのデータ構造

みんなのデータ構造

作者:Pat Morin
発売日: 2018/07/20
メディア: 単行本（ソフトカバー）

この本に載ってる（古い版？は無料のpdfが見れる）

*2:https://kazuma8128.hatenablog.com/entry/2018/05/06/022654 ここも詳しい