結果

問題 No.3082 Make Palindromic Multiple(Judge)
コンテスト
ユーザー 👑 binap
提出日時 2025-03-28 02:00:55
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 982 bytes
コンパイル時間 413 ms
コンパイル使用メモリ 82,012 KB
実行使用メモリ 121,328 KB
最終ジャッジ日時 2025-04-16 09:39:35
合計ジャッジ時間 15,703 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 71 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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")
0