結果

問題 No.515 典型LCP
コンテスト
ユーザー lam6er
提出日時 2025-04-15 20:54:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,777 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 142,840 KB
最終ジャッジ日時 2025-04-15 20:57:08
合計ジャッジ時間 4,979 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    strings = []
    for _ in range(N):
        s = input[ptr].strip()
        strings.append(s)
        ptr += 1
    M = int(input[ptr])
    x = int(input[ptr+1])
    d = int(input[ptr+2])
    ptr += 3

    mod1 = 10**18 + 3
    base1 = 911382629
    mod2 = 10**18 + 7
    base2 = 3571428571

    prefix_hash1 = []
    prefix_hash2 = []
    lens = []

    for s in strings:
        n = len(s)
        lens.append(n)
        h1 = [0] * (n + 1)
        h2 = [0] * (n + 1)
        for i in range(n):
            c = ord(s[i]) - ord('a') + 1
            h1[i+1] = (h1[i] * base1 + c) % mod1
            h2[i+1] = (h2[i] * base2 + c) % mod2
        prefix_hash1.append(h1)
        prefix_hash2.append(h2)

    n = N
    max_x = n * (n - 1)
    total = 0

    for _ in range(M):
        # Generate i and j
        div = (n - 1)
        xi = x // div
        xj = x % div
        i_val = xi + 1
        j_val = xj + 1

        if i_val > j_val:
            i_val, j_val = j_val, i_val
        else:
            j_val += 1

        a = i_val - 1
        b = j_val - 1

        len_a = lens[a]
        len_b = lens[b]
        min_len = min(len_a, len_b)
        low = 0
        high = min_len
        ans = 0
        h1_a = prefix_hash1[a]
        h1_b = prefix_hash1[b]
        h2_a = prefix_hash2[a]
        h2_b = prefix_hash2[b]

        while low <= high:
            mid = (low + high) // 2
            if h1_a[mid] == h1_b[mid] and h2_a[mid] == h2_b[mid]:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1

        total += ans

        x = (x + d) % max_x

    print(total)

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