ハッシュ

ローリングハッシュ

数列をハッシュにする方法

Zobrist Hash

状態をハッシュにする方法

code:python

import random

N = 5

# 出現要素にランダムな整数を割り当て

table = {}

for e in A + B:

def make_hash(arr):

"""リスト arr について、先頭 i 項のハッシュを前計算"""

setA = set()

for a in arr:

if a in setA:

else:

setA.add(a)

return hashA

hashA = make_hash(A)

hashB = make_hash(B)

# A, Bそれぞれの先頭 i 項からなる集合が一致するかを判定

for i in range(1, 6):

例2: multisetをハッシュ化する

配列Aのある部分配列と、配列Bのある部分配列とが、ソートすると一致するか（＝multisetが同じか）を判定する

Zobrist Hashでxorにしている部分を和にすると、setではなくmultisetをハッシュ化できるようになるのがポイント。ハッシュ値の差をとることで、部分配列のハッシュ値もわかる

code:python

P = 8128812800000059

def hs(arr):

"""

ハッシュ値のリストLを作成

"""

s = 0

for i, a in enumerate(arr):

s = (s + a * (a + 1346) * (a + 9185)) % P

L.append(s)

return L

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

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

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

hashA = hs(A)

hashB = hs(B)

for q in range(Q):

l, r, L, R = map(int, input().split())

if val1 == val2:

print('Yes')

else:

print('No')

参考URL