結果
問題 |
No.3091 The Little Match Boy
|
ユーザー |
![]() |
提出日時 | 2025-04-06 16:41:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 397 ms / 2,000 ms |
コード長 | 4,266 bytes |
コンパイル時間 | 472 ms |
コンパイル使用メモリ | 82,724 KB |
実行使用メモリ | 96,696 KB |
最終ジャッジ日時 | 2025-04-06 16:41:39 |
合計ジャッジ時間 | 13,986 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 62 |
ソースコード
#yukicoder3091 The Little Match Boy #Rolling Hash mod (1 << 61) - 1 import random class Rolling_Hash: def __init__(self, base = 'random'): self.mod = (1 << 61) - 1 self.base = base if base != 'random' else random.randint(200, self.mod - 1) self._B, self._m30, self._m31 = [1], (1 << 30) - 1, (1 << 31) - 1 def _mul(self, a, b): p, q, d, e = a >> 31, b >> 31, a & self._m31, b & self._m31; m = p * e + q * d ans = p * q * 2 + (m >> 30) + ((m & self._m30) << 31) + d * e if 0 <= ans < self.mod: return ans r, s = ans >> 61, ans & self.mod return r + s if r + s < self.mod else r + s - self.mod def fact(self, n): #pow(base, n, mod) i = len(self._B) while len(self._B) <= n: self._B.extend([0] * len(self._B)) for i in range(i, len(self._B)): self._B[i] = self._mul(self._B[i - 1], self.base) return self._B[n] def hash(self, seq): #get sequence hash if isinstance(seq, str): seq = [ord(s) for s in seq] ans = 0 for num in seq: ans = self._mul(ans, self.base) + num if ans >= self.mod: ans -= self.mod return ans def build(self, seq, use_BIT = False): #数列を取り込み前計算 if isinstance(seq, str): seq = [ord(s) for s in seq] self._BIT, _ = use_BIT, self.fact(len(seq) + 1) if not self._BIT: self._H = [0] * (len(seq) + 1) for i in range( len(seq) ): self._H[i + 1] = self._mul(self._H[i], self.base) + seq[i] if self._H[i + 1] >= self.mod: self._H[i + 1] -= self.mod else: self._N, self._S = len(seq), seq[:] self.bit, H = [0] * (self._N + 1), [0] * (self._N + 1) for i in range(self._N): H[i + 1] = self._mul(H[i], self.base) + seq[i] if H[i + 1] >= self.mod: H[i + 1] -= self.mod for e in range( (self._N + 1).bit_length() ): d = 1 << e for Lt in range(0, self._N + 1 - d, d << 1): Rt = Lt + d; self.bit[Rt] = H[Rt] - self._mul(H[Lt], self._B[Rt - Lt]) if self.bit[Rt] < 0: self.bit[Rt] += self.mod def update(self, i, x): #seq[i] ← x (代入処理) BIT使用時限定 self._S[i], diff, i, j = x, x - self._S[i], i + 1, i + 1 if diff < 0: diff += self.mod while j <= self._N: self.bit[j] += self._mul(diff, self._B[j - i]) if self.bit[j] >= self.mod: self.bit[j] -= self.mod j += j & -j def fold(self, Lt, Rt): #seq[Lt, Rt)のhashを返す if not self._BIT: ans = self._H[Rt] - self._mul(self._H[Lt], self._B[Rt - Lt]) return ans if ans >= 0 else ans + self.mod else: ans, dL, dR = 0, Rt - Lt, 0 while Lt != Rt: if Lt > Rt: LSB = Lt & - Lt; ans -= self._mul(self.bit[Lt], self._B[dL]) if ans < 0: ans += self.mod Lt, dL = Lt - LSB, dL + LSB else: LSB = Rt & - Rt; ans += self._mul(self.bit[Rt], self._B[dR]) if ans >= self.mod: ans -= self.mod Rt, dR = Rt - LSB, dR + LSB return ans #入力受取 N, M = map(int, input().split()) S = list(map(int, input().split())) #1. 最終的な結果をシミュレート A = list(range(N)) for Si in S: A[Si - 1], A[Si] = A[Si], A[Si - 1] #2. RHにAの逆置換を乗せる nA = [0] * N for i, Ai in enumerate(A): nA[Ai] = i A = nA RH = Rolling_Hash(100) RH.build(A, True) #3. 上からシミュレート B = list(range(N)) C = [] for Si in S: #B[Si - 1]とB[Si]のswapを行わない場合、B[Si - 1]とB[Si]の結果が入れ替わる i, j = B[Si - 1], B[Si] #A[i], A[j]の値を入れ替え RH.update(i, A[j]) RH.update(j, A[i]) #total hashを取得 C.append( RH.fold(0, N) ) #入れ替えを元に戻す RH.update(i, A[i]) RH.update(j, A[j]) #次のマップへ B[Si - 1], B[Si] = B[Si], B[Si - 1] #答えを出力 C.sort() ans, left = 0, -1 for Ci in C: if left != Ci: left = Ci ans += 1 print(ans)