結果

問題 No.3082 Make Palindromic Multiple(Judge)
ユーザー 👑 binap
提出日時 2025-03-28 02:00:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,142 ms / 3,500 ms
コード長 982 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 82,500 KB
実行使用メモリ 121,716 KB
最終ジャッジ日時 2025-03-29 00:24:12
合計ジャッジ時間 16,901 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 71
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def pow_mod(n, k, MOD):
    if k == 0:
        return 1 % MOD
    res = 1 % MOD
    while k > 0:
        if k & 1:
            res *= n
            res %= MOD
        k >>= 1
        n = (n * n) % MOD
    return res
    
# MOD >= 2
def inv_mod(n, MOD):
    return pow_mod(n, MOD - 2, MOD)
K = int(input())
S_list = []
T_list = []
for i in range(K):
    s, t = input().split()
    S_list.append(s)
    T_list.append(int(t))
def is_palindrome(MOD, base):
    hash = [0, 0]
    for t in range(2):
        x = 0
        
        for i in range(K):
            sz = len(S_list[i])
            p = pow_mod(base, sz, MOD)
            q = pow_mod(p, T_list[i], MOD)
            
            y = 0
            for j in range(sz):
                y *= base
                y += ord(S_list[i][j])
                y %= MOD
            
            x = x * q + (y * (q - 1) % MOD) * inv_mod(p - 1, MOD)
            x %= MOD
    
        hash[t] = x
        
        S_list.reverse()
        T_list.reverse()
        for i in range(K):
            S_list[i] = S_list[i][::-1]
    
    if hash[0] == hash[1]:
        return True
    else:
        return False
if is_palindrome(999998003, 114514) and is_palindrome(999997967, 114514):
    print("Yes")
else:
    print("No")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0