結果

問題 No.515 典型LCP
ユーザー gew1fw
提出日時 2025-06-12 18:10:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,761 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 145,668 KB
最終ジャッジ日時 2025-06-12 18:12:20
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 2 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    MOD1 = 10**18 + 3
    BASE1 = 911382629
    MOD2 = 10**18 + 7
    BASE2 = 3571428571

    n = int(sys.stdin.readline())
    strs = []
    max_len = 0
    for _ in range(n):
        s = sys.stdin.readline().strip()
        strs.append(s)
        max_len = max(max_len, len(s))
    
    max_power = max_len
    pow1 = [1] * (max_power + 1)
    pow2 = [1] * (max_power + 1)
    for i in range(1, max_power + 1):
        pow1[i] = (pow1[i-1] * BASE1) % MOD1
        pow2[i] = (pow2[i-1] * BASE2) % MOD2
    
    lens = []
    full_hash1 = []
    full_hash2 = []
    prefix_ph1 = []
    prefix_ph2 = []
    for s in strs:
        l = len(s)
        lens.append(l)
        ph1 = [0] * l
        ph2 = [0] * l
        if l > 0:
            ph1[0] = (ord(s[0]) - ord('a') + 1) % MOD1
            ph2[0] = (ord(s[0]) - ord('a') + 1) % MOD2
            for i in range(1, l):
                ph1[i] = (ph1[i-1] * BASE1 + (ord(s[i]) - ord('a') + 1)) % MOD1
                ph2[i] = (ph2[i-1] * BASE2 + (ord(s[i]) - ord('a') + 1)) % MOD2
            full_h1 = ph1[-1]
            full_h2 = ph2[-1]
        else:
            full_h1 = 0
            full_h2 = 0
        full_hash1.append(full_h1)
        full_hash2.append(full_h2)
        prefix_ph1.append(ph1)
        prefix_ph2.append(ph2)
    
    M, x, d = map(int, sys.stdin.readline().split())
    current_x = x
    n_val = n
    sum_lcp = 0
    
    for _ in range(M):
        div = n_val - 1
        i = (current_x // div) + 1
        j = (current_x % div) + 1
        if i > j:
            i, j = j, i
        else:
            j += 1
        i0 = i - 1
        j0 = j - 1
        
        len_i = lens[i0]
        len_j = lens[j0]
        if full_hash1[i0] == full_hash1[j0] and full_hash2[i0] == full_hash2[j0]:
            sum_lcp += min(len_i, len_j)
        else:
            low = 0
            high = min(len_i, len_j)
            max_m = 0
            ph1_i = prefix_ph1[i0]
            ph1_j = prefix_ph1[j0]
            ph2_i = prefix_ph2[i0]
            ph2_j = prefix_ph2[j0]
            while low <= high:
                mid = (low + high) // 2
                if mid == 0:
                    max_m = 0
                    low = mid + 1
                else:
                    h1_i = ph1_i[mid-1]
                    h1_j = ph1_j[mid-1]
                    h2_i = ph2_i[mid-1]
                    h2_j = ph2_j[mid-1]
                    if h1_i == h1_j and h2_i == h2_j:
                        max_m = mid
                        low = mid + 1
                    else:
                        high = mid - 1
            sum_lcp += max_m
        
        current_x = (current_x + d) % (n_val * (n_val - 1))
    
    print(sum_lcp)

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