結果

問題 No.515 典型LCP
ユーザー lam6er
提出日時 2025-04-15 21:20:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,857 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 136,096 KB
最終ジャッジ日時 2025-04-15 21:26:17
合計ジャッジ時間 4,805 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    strings = []
    len_list = []
    for _ in range(N):
        s = input[ptr]
        ptr += 1
        strings.append(s)
        len_list.append(len(s))
    
    # Precompute hash values for each string using two different bases and mods
    base1 = 911382629
    mod1 = 10**18 + 3
    base2 = 3571428571
    mod2 = 10**18 + 7
    
    hash1 = []
    hash2 = []
    for s in strings:
        n = len(s)
        h1 = [0] * (n + 1)
        h2 = [0] * (n + 1)
        for i in range(n):
            h1[i+1] = (h1[i] * base1 + ord(s[i])) % mod1
            h2[i+1] = (h2[i] * base2 + ord(s[i])) % mod2
        hash1.append(h1)
        hash2.append(h2)
    
    M, x, d = map(int, input[ptr:ptr+3])
    ptr +=3
    
    total = 0
    n = N
    for _ in range(M):
        div = n - 1
        i0 = x // div
        j0 = x % div
        i = i0 + 1
        j = j0 + 1
        
        if i > j:
            i, j = j, i
        else:
            j += 1
        
        # Convert to 0-based index
        i_idx = i - 1
        j_idx = j - 1
        
        len_i = len_list[i_idx]
        len_j = len_list[j_idx]
        max_possible = min(len_i, len_j)
        
        # Binary search for LCP
        low, high = 0, max_possible
        ans = 0
        h1_i = hash1[i_idx]
        h1_j = hash1[j_idx]
        h2_i = hash2[i_idx]
        h2_j = hash2[j_idx]
        while low <= high:
            mid = (low + high) // 2
            if h1_i[mid] == h1_j[mid] and h2_i[mid] == h2_j[mid]:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        total += ans
        
        # Update x for next query
        x = (x + d) % (n * (n - 1))
    
    print(total)

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