ハッシュ
ローリングハッシュ
数列をハッシュにする方法
Zobrist Hash
状態をハッシュにする方法
ABC250E 。配列A、配列Bそれぞれの先頭 i 項からなる集合が一致するかを判定する code:python
import random
N = 5
# 出現要素にランダムな整数を割り当て
table = {}
for e in A + B:
tablee = random.randrange(1 << 60) def make_hash(arr):
"""リスト arr について、先頭 i 項のハッシュを前計算"""
setA = set()
for a in arr:
if a in setA:
else:
setA.add(a)
hashA.append(hashA-1 ^ tablea) return hashA
hashA = make_hash(A)
hashB = make_hash(B)
# A, Bそれぞれの先頭 i 項からなる集合が一致するかを判定
for i in range(1, 6):
print("Yes" if hashAi == hashBi else "No") 例2: multisetをハッシュ化する
配列Aのある部分配列と、配列Bのある部分配列とが、ソートすると一致するか(=multisetが同じか)を判定する
Zobrist Hashでxorにしている部分を和にすると、setではなくmultisetをハッシュ化できるようになるのがポイント。ハッシュ値の差をとることで、部分配列のハッシュ値もわかる
code:python
P = 8128812800000059
def hs(arr):
"""
ハッシュ値のリストLを作成
L0 = 0, L1 = mutliset{arr0}のハッシュ、L2 = multiset{arr0, arr1}のハッシュ """
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):
# Q: multiset{Al, Al+1, ..., Ar}と # multiset{BL, BL+1, ..., BR}とが同じか? l, r, L, R = map(int, input().split())
val1 = (hashAr - hashAl - 1 + P) % P val2 = (hashBR - hashBL - 1 + P) % P if val1 == val2:
print('Yes')
else:
print('No')
参考URL