結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
ユーザー roaris
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

import sys
input = sys.stdin.readline
from collections import *
class RollingHash:
def __init__(self, s):
self.base = 31
self.mod = 10**9+7
self.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.mod
N = 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 = h
nh -= (ord(S[i])-ord('a'))*rh.power[n-1-i]%rh.mod
nh %= rh.mod
nh -= (ord(S[i+1])-ord('a'))*rh.power[n-2-i]%rh.mod
nh %= rh.mod
nh += (ord(S[i+1])-ord('a'))*rh.power[n-1-i]%rh.mod
nh %= rh.mod
nh += (ord(S[i])-ord('a'))*rh.power[n-2-i]%rh.mod
nh %= rh.mod
if nh in ws:
print('Yes')
break
else:
print('No')
ws.add(h)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0