結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー navel_tos
提出日時 2025-11-29 12:42:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 368 ms / 2,000 ms
コード長 7,815 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 291 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 227,016 KB
最終ジャッジ日時 2025-11-29 12:43:05
合計ジャッジ時間 20,916 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#yukicoder570

'''
#A-D 省略

#E
#入力受取 Aをソート
N, M, K = map(int, input().split())
A = sorted(int(Ai) for Ai in input().split())
MOD = 998244353

#sub[i]: ドミノiとの大きさの差がK以下の[Lt, Rt)
sub: list[tuple[int, int]] = [(0, 0)] * N
for i in range(N):
    for Lt in range(i - 1, -2, -1):
        if Lt == -1 or abs(A[Lt] - A[i]) > K:
            break
    Lt += 1
    for Rt in range(i + 1, N + 1, +1):
        if Rt == N or abs(A[Rt] - A[i]) > K:
            break
    sub[i] = (Lt, Rt)

#累積和DP
DP: list[int] = [1] * N
C: list[int] = [0] * (N + 1)
for _ in range(M - 1):
    for i in range(N):
        C[i + 1] = (C[i] + DP[i]) % MOD
    for i, (Lt, Rt) in enumerate(sub):
        DP[i] = C[Rt] - C[Lt]
ans: int = sum(DP) % MOD
if ans < 0:
    ans += MOD
print(ans)
'''

#F
#Rolling Hash
#Reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
from random import randrange as _RollingHash_randrange
_RollingHash_base = _RollingHash_randrange(~ (- 1 << 61))
class RollingHash:
    '''
    Rolling Hash for codon, PyPy3
    法2 ** 61 - 1の下、文字列のハッシュを計算します。

    base: 基数 指定がない場合、[0, 2 ** 61 - 1)から乱択
    '''
    base: int
    _builded: bool
    _B: list[int]
    _H: list[int]
    __slots__ = ('base', '_builded', '_B', '_H')
    def __init__(self, base: int = -1) -> None:
        self.base: int = base if 0 <= base < 0x1FFFFFFFFFFFFFFF else _RollingHash_base
        self._B: list[int] = [1]
    #内部関数
    def _mul(self, x: int, y: int) -> int:
        div_x, mod_x = x >> 31, x & 0x7FFFFFFF
        div_y, mod_y = y >> 31, y & 0x7FFFFFFF
        m: int = div_x * mod_y + div_y * mod_x
        ans: int = 2 * div_x * div_y + (m >> 30) + ((m & 0x3FFFFFFF) << 31) + mod_x * mod_y
        if ans < 0x1FFFFFFFFFFFFFFF:
            return ans
        div_ans, mod_ans = ans >> 61, ans & 0x1FFFFFFFFFFFFFFF
        ans2: int = div_ans + mod_ans
        return ans2 if ans2 < 0x1FFFFFFFFFFFFFFF else ans2 - 0x1FFFFFFFFFFFFFFF
    def _build_B(self, x: int) -> None:
        if x >= len(self._B):
            if (x + 1) / len(self._B) < 1.1:
                for _ in range(x + 1 - len(self._B)):
                    self._B.append(self._mul(self._B[-1], self.base))
            else:
                new_B: list[int] = [1] * (x + 1)
                for i, Bi in enumerate(self._B):
                    new_B[i] = Bi
                for i in range(len(self._B), x + 1):
                    new_B[i] = self._mul(new_B[i - 1], self.base)
                self._B = new_B
    def _RH(self, A, k: int) -> list[int]:
        ans: list[int] = [0] * (len(A) - k + 1)
        cnt: int = 0
        pow_base: int = 1
        for i in range(k):
            Ai: int = ord(A[i]) if isinstance(A[i], str) else A[i]
            cnt: int = self._mul(cnt, self.base) + Ai
            if cnt >= 0x1FFFFFFFFFFFFFFF:
                cnt -= 0x1FFFFFFFFFFFFFFF
            pow_base: int = self._mul(pow_base, self.base)
        ans[0] = cnt
        for Li in range(len(A) - k):
            A_back: int = ord(A[Li    ]) if isinstance(A[Li    ], str) else A[Li    ]
            A_now:  int = ord(A[Li + k]) if isinstance(A[Li + k], str) else A[Li + k]
            cnt: int = self._mul(cnt, self.base) + A_now - self._mul(A_back, pow_base)
            if cnt >= 0x1FFFFFFFFFFFFFFF:
                cnt -= 0x1FFFFFFFFFFFFFFF
            if cnt < 0:
                cnt += 0x1FFFFFFFFFFFFFFF
            ans[Li + 1] = cnt
        return ans
    def _build_array(self, A) -> None:
        self._builded: bool = True
        self._H: list[int] = [0] * (len(A) + 1)
        self._build_B(len(A))
        for i, Ai in enumerate(A):
            Bi: int = ord(Ai) if isinstance(Ai, str) else Ai
            self._H[i + 1] = self._mul(self._H[i], self.base) + Bi
            if self._H[i + 1] >= 0x1FFFFFFFFFFFFFFF:
                self._H[i + 1] -= 0x1FFFFFFFFFFFFFFF

    #基本機能
    def hash(self, A) -> int:
        '現在の基数を用い、Aのハッシュ値を計算します。'
        ans: int = 0
        for Ai in A:
            Bi: int = ord(Ai) if isinstance(Ai, str) else Ai
            ans: int = self._mul(ans, self.base) + Bi
            if ans >= 0x1FFFFFFFFFFFFFFF:
                ans -= 0x1FFFFFFFFFFFFFFF
        return ans
    def rolling_hash(self, A, k: int) -> list[int]:
        '0 <= i < len(A) - k + 1 において、A[i: i + k]のハッシュ値を計算します。'
        assert 0 <= k <= len(A)
        return self._RH(A, k)
    def build(self, A) -> None:
        'Aのハッシュの前計算を行います。'
        self._build_array(A)
    def fold(self, Lt: int, Rt: int) -> int:
        'build(A)によるAの前計算の下、A[Lt: Rt]のハッシュをO(1)で取得します。'
        assert self._builded == True
        assert 0 <= Lt and Rt < len(self._H)
        if Lt >= Rt:
            return 0
        ans: int = self._H[Rt] - self._mul(self._H[Lt], self._B[Rt - Lt])
        return ans if ans >= 0 else ans + 0x1FFFFFFFFFFFFFFF


#入力受取
N = int(input())
A = [int(Ai) for Ai in input().split()]

#D[i]: A[i + 1] - A[i]
D: list[int] = [A[i + 1] - A[i] for i in range(N - 1)]
n: int = len(D)


#Dの回文の個数を数える  manacherでO(N) RHでO(NlogN)
#RHの制約上、入力は[0, 2**61 - 1)に収めないといけないのでDを補正
def count_palindrome_RH(D):
    ans: int = 0
    base: int = 100
    RH = RollingHash(base)
    revRH = RollingHash(base)
    for i in range(n):
        D[i] %= ~(-1 << 61)
        if D[i] < 0:
            D[i] += ~(-1 << 61)  #for codon
    RH.build(D)
    revRH.build(D[::-1])
    #1. D[i]を中心とする奇数長の回文
    for i in range(n):
        #回文半径をd文字(d >= 1)としたとき、D[i: i + d] == rev(D[i + 1 - d: i + 1]) を判定
        #D[Lt: Rt] → revD[n - Rt: n - Lt] に注意
        ok: int = 1
        ng: int = min(n - i + 1, i + 2)
        while abs(ok - ng) > 1:
            mid: int = (ok + ng) >> 1
            if RH.fold(i, i + mid) == revRH.fold(n - (i + 1), n - (i + 1 - mid)):
                ok = mid
            else:
                ng = mid
        ans += ok

    #2. D[i]とD[i + 1]の間を中心とする偶数長の回文
    for i in range(n - 1):
        #回文半径をd文字(d >= 0)としたとき、D[i + 1: i + 1 + d] == rev(D[i + 1 - d: i + 1]) を判定
        ok: int = 0
        ng: int = min(n - i, i + 2)
        while abs(ok - ng) > 1:
            mid: int = (ok + ng) >> 1
            if RH.fold(i + 1, i + 1 + mid) == revRH.fold(n - (i + 1), n - (i + 1 - mid)):
                ok = mid
            else:
                ng = mid
        ans += ok
    return ans


#TLEしたのでmanacher
#Reference: https://tjkendev.github.io/procon-library/python/string/manacher.html
def manacher(S) -> list[int]:
    '''
    S: str | list[str] | list[int] として、Sの最長回文を求めます。
    A[i << 1]: S[i]を中心とする奇数長の最大回文
    A[i << 1 | 1]: S[i + 1: i + 1]を中心とする偶数長の最大回文

    制約: S[i]はstr または 非負整数
    '''
    C: list[int] = [-1] * (2 * len(S) - 1)
    for i, s in enumerate(S):
        Si: int = ord(s) if isinstance(s, str) else int(s)
        C[i << 1] = Si
    N: int = len(C)
    A: list[int] = [0] * N
    i = j = 0
    while i < N:
        while j <= i < N - j and C[i - j] == C[i + j]:
            j += 1
        A[i] = j
        k: int = 1
        while j - A[i - k] > k <= i < N - k:
            A[i + k] = A[i - k]
            k += 1
        i += k
        j -= k
    for i in range(N):
        if i & 1 == A[i] & 1:
            A[i] -= 1
    return A


#ans: int = N + count_palindrome_RH(D)
ans: int = N + sum(-(-Ai >> 1) for Ai in manacher(D))
print(ans)
0