結果

問題 No.515 典型LCP
ユーザー lam6er
提出日時 2025-03-31 17:22:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,144 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 138,800 KB
最終ジャッジ日時 2025-03-31 17:23:44
合計ジャッジ時間 4,858 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 2 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

    MOD1 = 10**18 + 3
    MOD2 = 10**18 + 7
    BASE1 = 911382629
    BASE2 = 3571428571

    prefix_h1 = []
    prefix_h2 = []
    len_list = []
    for s in strings:
        l = len(s)
        len_list.append(l)
        ph1 = [0] * (l + 1)
        ph2 = [0] * (l + 1)
        for i in range(l):
            c = ord(s[i]) - ord('a')
            ph1[i+1] = (ph1[i] * BASE1 + c) % MOD1
            ph2[i+1] = (ph2[i] * BASE2 + c) % MOD2
        prefix_h1.append(ph1)
        prefix_h2.append(ph2)

    total = 0
    current_x = x
    n_val = n
    mod_x = n_val * (n_val - 1)
    for _ in range(M):
        # Generate i and j
        tmp = current_x
        divisor = n_val - 1
        if divisor == 0:
            i_val = 1
            j_val = 1
        else:
            i_val = (tmp // divisor) + 1
            j_val = (tmp % divisor) + 1
        # Adjust i_val and j_val
        if i_val > j_val:
            i_val, j_val = j_val, i_val
        else:
            j_val += 1
        # Compute indexes
        i_idx = i_val - 1
        j_idx = j_val - 1
        # Calculate LCP
        a_len = len_list[i_idx]
        b_len = len_list[j_idx]
        max_k = min(a_len, b_len)
        a_ph1 = prefix_h1[i_idx]
        a_ph2 = prefix_h2[i_idx]
        b_ph1 = prefix_h1[j_idx]
        b_ph2 = prefix_h2[j_idx]
        ans_k = 0
        if max_k > 0:
            bit = 1 << (max_k.bit_length() - 1)
            while bit > 0:
                current_k = ans_k | bit
                if current_k > max_k:
                    bit >>= 1
                    continue
                if (a_ph1[current_k] == b_ph1[current_k] and
                    a_ph2[current_k] == b_ph2[current_k]):
                    ans_k = current_k
                bit >>= 1
        total += ans_k
        # Update x
        current_x = (current_x + d) % mod_x

    print(total)

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