結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:14:28 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,235 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 82,200 KB |
実行使用メモリ | 226,800 KB |
最終ジャッジ日時 | 2024-06-26 17:05:20 |
合計ジャッジ時間 | 26,739 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 46 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import *class RollingHash:def __init__(self, s):self.base = 31self.mod = 10**9+7self.acc = [0]self.power = [1]for i in range(len(s)):self.acc.append((self.acc[-1]*self.base%self.mod+(ord(s[i])-ord('a')))%self.mod)self.power.append(self.power[-1]*self.base%self.mod)def get(self, l, r):return (self.acc[r]-self.acc[l]*self.power[r-l])%self.modN = int(input())ws = set()for _ in range(N):S = input()[:-1]n = len(S)rh = RollingHash(S)h = rh.get(0, n)if h in ws:print('Yes')else:for i in range(n-1):nh = hnh -= (ord(S[i])-ord('a'))*rh.power[n-1-i]%rh.modnh %= rh.modnh -= (ord(S[i+1])-ord('a'))*rh.power[n-2-i]%rh.modnh %= rh.modnh += (ord(S[i+1])-ord('a'))*rh.power[n-1-i]%rh.modnh %= rh.modnh += (ord(S[i])-ord('a'))*rh.power[n-2-i]%rh.modnh %= rh.modif nh in ws:print('Yes')breakelse:print('No')ws.add(h)