結果

問題 No.3091 The Little Match Boy
ユーザー navel_tos
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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)
0