---
tags: 競プロ
---
# 集合をハッシュする (Zobrist hashing)

## Zobrist hashing とは

https://en.wikipedia.org/wiki/Zobrist_hashing

チェスをするコンピュータを作るときにチェスの状態をハッシュするために Zobrist さんが作ったハッシュ方法らしいです。

## できること

- 集合をハッシュすることで、集合の一致判定が $O(1)$ 時間になります。
- 集合 $A$ に $1$ 要素 追加 / 削除 したときのハッシュを $O(1)$ 時間で計算できます。
- 集合 $A$ のハッシュと集合 $B$ のハッシュから、対称差(XOR) $A\triangle B$ のハッシュを $O(1)$ 時間で計算できます。

## やり方

1. 集合の要素として出てくる値にランダムな整数を割り当てます。
2. 集合のハッシュは、その集合の各要素に割り当てられた整数の総 XOR です。

### 例

#### 1. 集合の要素として出てくる値 : $a, b, c$ にランダムな整数を割り当てます。

$$
\text{table}[a] := 10111111\\
\text{table}[b] := 10010000\\
\text{table}[c] := 01101110\\
$$

#### 2. 集合のハッシュは、その集合の各要素に割り当てられた整数の総 XOR です。

$$
\gdef\hash#1{\text{hash}(\{#1\})}
\begin{aligned}
\hash{} &= 00000000\\
\hash{a} &= 10111111\\
\hash{b} &= 10010000\\
\hash{c} &= 01101110\\
\hash{a, b} &= 00101111\\
\hash{a, c} &= 11010001\\
\hash{b, c} &= 11111110\\
\hash{a, b, c} &= 01000001\\
\end{aligned}
$$

## [ABC250 E - Prefix Equality](https://atcoder.jp/contests/abc250/tasks/abc250_e)

集合の比較なら Zobrist hashing ですね！
先頭 $i$ 項のハッシュを前計算しておけば、クエリ部分は $O(1)$ 時間 / クエリ になります。

from random import *

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# ランダムな整数を割り当て
table = {}
for a in A:
    table[a] = randrange(1 << 60)
for b in B:
    table[b] = randrange(1 << 60)

# 先頭 i 項のハッシュを前計算
hashA = [0]
setA = set()
for a in A:
    if a in setA:
        hashA.append(hashA[-1])
    else:
        setA.add(a)
        hashA.append(hashA[-1] ^ table[a])

hashB = [0]
setB = set()
for b in B:
    if b in setB:
        hashB.append(hashB[-1])
    else:
        setB.add(b)
        hashB.append(hashB[-1] ^ table[b])

# クエリに答える
Q = int(input())
for i in range(Q):
    x, y = map(int, input().split())
    print("Yes" if hashA[x] == hashB[y] else "No")

https://atcoder.jp/contests/abc250/submissions/31642562

## チェスの盤面をハッシュする

集合のハッシュができることは分かりましたが、チェスの盤面をハッシュするにはどうすればいいでしょうか？

チェスの盤面をうまく集合として表しさえすればいいですね。

そこで、(駒の種類, 駒の色, 駒の位置) を $1$ 要素にして、これらの集合でチェスの盤面を表してみましょう。駒の種類は $6$ 種類、駒の色は $2$ 種類、駒の位置は $64$ 種類あるので、$6 \times 2 \times 64 = 768$ 個のランダムな整数を割り当てれば、チェスの盤面をハッシュすることができます。

ある盤面のハッシュから次の盤面のハッシュを計算するには、動いた駒の動く前の位置での値を XOR して引き、動いた後の位置での値を XOR して足せば良いです。

このように、**集合の $1$ つの要素だけが変化する**ような場合では、Zobrist hashing が役に立ちがちです。

## [モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238) G - Cubic?](https://atcoder.jp/contests/abc238/tasks/abc238_g)

### 立方数ではなく平方数である場合

$A$ を左から累積積を計算し、平方数で割れるだけ割ったものを $B$ とします。すなわち、素因数分解をしたあと、指数の累積和${}\bmod 2$ をしたものです。
これが $B_{L-1}$ と $B_R$ で一致していれば、その間の積 $A_L \times \dots \times A_R$ は平方数です。

しかし、累積積は非常に大きくなるので $B$ を直接計算することはできません。
そこで、Zobrist hashing を使ってみましょう。各素因数にランダムな整数を割り当てて、その素因数が入っていたら XOR という感じでハッシュを計算します。

これで、$O(N(\log N + \log A_\max) + A_\max + Q)$ 時間で解くことができます。

### 立方数である場合

素因数分解をしたあと、指数の累積和${}\bmod 3$ をしたものを $B$ とします。
この場合、各素因数にランダムな整数を割り当てて、その素因数が入っていたら XOR という方法は使えません。なぜなら、$2$ が $2$ 個入っているからといって $2$ に割り当てられた整数を $2$ 回 XOR すると、元に戻ってしまうからです。

しかし、チェスの盤面のハッシュができるならこれもハッシュできるはずです。うまく集合として表しましょう。

(素因数, 指数) を $1$ 要素にして、これらの集合でチェスの盤面を表すのが良いですね。
つまり、$0$ 回掛かっている場合と $1$ 回掛かっている場合と $2$ 回掛かっている場合で別の乱数を用意するということです。
( $0$ 回掛かっている場合は集合に入れないものとすれば、$0$ 回掛かっている場合の乱数は要らなくなります。)

import sys
from random import randrange
input = sys.stdin.readline
MAX = 10 ** 6

N, Q = map(int, input().split())
A = list(map(int, input().split()))

# ランダムな整数を割り当てる
table = [[0] * (MAX + 1)] * 3
table[1] = [randrange(1 << 60) for _ in range(MAX + 1)]
table[2] = [randrange(1 << 60) for _ in range(MAX + 1)]

# 線形ふるい
primes = []
min_factor = [0] * (MAX + 1)
for i in range(2, MAX + 1):
    if min_factor[i] == 0:
        primes.append(i)
        min_factor[i] = i
    f = min_factor[i]
    for p in primes:
        j = i * p
        if p > f or j > MAX:
            break
        min_factor[j] = p

# ハッシュを計算
B = [0]
cnt = [0] * (MAX + 1) # 素数の出てきた回数
h = 0

def add(p: int): # 素数を追加
    global h
    h ^= table[cnt[p]][p]
    cnt[p] += 1
    if cnt[p] == 3:
        cnt[p] = 0
    h ^= table[cnt[p]][p]

for a in A:
    while a > 1:
        p = min_factor[a]
        add(p)
        a //= p
    B.append(h)

# クエリを処理
for _ in range(Q):
    L, R = map(int, input().split())
    print("Yes" if B[L - 1] == B[R] else "No")

https://atcoder.jp/contests/abc238/submissions/31642741