結果

問題 No.515 典型LCP
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:02:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,924 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 134,628 KB
最終ジャッジ日時 2025-06-12 20:07:58
合計ジャッジ時間 4,774 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    from sys import stdin

    MOD1 = 10**18 + 3
    BASE1 = 911382629
    MOD2 = 10**18 + 7
    BASE2 = 3571428571

    n = int(stdin.readline())
    strings = [stdin.readline().strip() for _ in range(n)]

    # Precompute hashes for each string
    hash1 = []
    hash2 = []
    for s in strings:
        h1 = [0]
        h2 = [0]
        for c in s:
            next_h1 = (h1[-1] * BASE1 + ord(c)) % MOD1
            next_h2 = (h2[-1] * BASE2 + ord(c)) % MOD2
            h1.append(next_h1)
            h2.append(next_h2)
        hash1.append(h1)
        hash2.append(h2)

    M, x, d = map(int, stdin.readline().split())

    total = 0
    current_x = x
    n_minus_1 = n - 1
    max_x = n * (n_minus_1)

    for _ in range(M):
        # Compute i and j
        quotient, remainder = divmod(current_x, n_minus_1)
        i = quotient + 1
        j = remainder + 1

        if i > j:
            i, j = j, i
        else:
            j += 1

        # Ensure i < j
        if j > n:
            j = n

        # Convert to 0-based indices
        i_idx = i - 1
        j_idx = j - 1

        if i_idx >= j_idx:
            # Swap if necessary
            i_idx, j_idx = j_idx, i_idx

        s_i = strings[i_idx]
        s_j = strings[j_idx]

        h1_i = hash1[i_idx]
        h1_j = hash1[j_idx]
        h2_i = hash2[i_idx]
        h2_j = hash2[j_idx]

        min_len = min(len(s_i), len(s_j))
        low = 0
        high = min_len
        lcp = 0

        while low <= high:
            mid = (low + high) // 2
            if mid > min_len:
                high = mid - 1
                continue
            if h1_i[mid] == h1_j[mid] and h2_i[mid] == h2_j[mid]:
                lcp = mid
                low = mid + 1
            else:
                high = mid - 1

        total += lcp

        current_x = (current_x + d) % max_x

    print(total)

if __name__ == "__main__":
    main()
0