結果

問題 No.515 典型LCP
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:54:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,336 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,036 KB
実行使用メモリ 101,556 KB
最終ジャッジ日時 2025-06-12 12:57:59
合計ジャッジ時間 4,938 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline())
    strings = [sys.stdin.readline().strip() for _ in range(n)]
    base = 911382629
    mod = 10**18 + 3

    prefix_hashes = []
    lengths = []
    for s in strings:
        m = len(s)
        lengths.append(m)
        ph = [0] * (m + 1)
        for i in range(m):
            ph[i+1] = (ph[i] * base + ord(s[i])) % mod
        prefix_hashes.append(ph)

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

    for _ in range(M):
        current_x = x
        div = n - 1
        i = (current_x // div) + 1
        j_remainder = current_x % div
        j = j_remainder + 1

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

        a = i - 1
        b = j - 1

        ph_a = prefix_hashes[a]
        ph_b = prefix_hashes[b]
        len_a = lengths[a]
        len_b = lengths[b]
        max_possible = min(len_a, len_b)

        low, high, res = 0, max_possible, 0
        while low <= high:
            mid = (low + high) // 2
            if ph_a[mid] == ph_b[mid]:
                res = mid
                low = mid + 1
            else:
                high = mid - 1

        sum_lcp += res
        x = (current_x + d) % (n * (n - 1))

    print(sum_lcp)

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