結果

問題 No.515 典型LCP
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:09:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,610 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 102,444 KB
最終ジャッジ日時 2025-03-20 21:10:42
合計ジャッジ時間 14,325 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

base = 911382629
mod = 10**18 + 3

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    n = int(data[ptr])
    ptr += 1
    
    strings = []
    prefix_hashes = []
    
    for _ in range(n):
        s = data[ptr]
        ptr +=1
        m = len(s)
        h = [0] * (m + 1)
        for i in range(m):
            c = ord(s[i]) - ord('a') + 1
            h[i+1] = (h[i] * base + c) % mod
        strings.append(s)
        prefix_hashes.append(h)
    
    m_queries = int(data[ptr])
    x = int(data[ptr+1])
    d = int(data[ptr+2])
    ptr +=3
    
    sum_result = 0
    modulus = n * (n - 1)
    
    for _ in range(m_queries):
        current_x = x
        n_minus_1 = n - 1
        i_part = (current_x // n_minus_1) + 1
        j_part = (current_x % n_minus_1) + 1
        
        if i_part > j_part:
            i = j_part
            j = i_part
        else:
            i = i_part
            j = j_part + 1
        
        a = i - 1
        b = j - 1
        
        len_a = len(strings[a])
        len_b = len(strings[b])
        min_len = min(len_a, len_b)
        
        ha = prefix_hashes[a]
        hb = prefix_hashes[b]
        
        low = 0
        high = min_len
        best = 0
        
        while low <= high:
            mid = (low + high) // 2
            if ha[mid] == hb[mid]:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        
        sum_result += best
        
        x = (current_x + d) % modulus
    
    print(sum_result)

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