結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー |
|
提出日時 | 2023-11-29 15:39:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,296 ms / 3,000 ms |
コード長 | 2,637 bytes |
コンパイル時間 | 393 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 415,612 KB |
最終ジャッジ日時 | 2024-09-26 13:28:40 |
合計ジャッジ時間 | 110,112 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,mathinput = sys.stdin.readlineN = int(input())class Rolling_hash():def __init__(self,S,mod_list = [1000000009,998244353,3000012541],base_num_list=[500009,500029,500041]):self.n = len(mod_list)self.S = Sself.N = len(self.S)self.H = [[0]*(self.N+1) for _ in range(self.n)]self.b_inv = [[1]*self.N for _ in range(self.n)]self.b = [[1]*self.N for _ in range(self.n)]self.mod_list = mod_listfor j in range(self.n):tb = base_num_list[j]base_num = base_num_list[j]mod = mod_list[j]tb_inv = 1base_inv = pow(base_num,mod-2,mod)tH = self.S[0]self.H[j][1] = tHfor i in range(self.N-1):tH = (tH + self.S[i+1]*tb)%modself.H[j][i+2] = tHself.b[j][i+1] = tbtb = (tb*base_num)%modtb_inv *= base_invtb_inv %= modself.b_inv[j][i+1] = tb_inv# self.b[j][i+1] = tbdef query(self,j,l,r):if l==r:return 0tmp = (self.H[j][r]-self.H[j][l])*self.b_inv[j][l]%self.mod_list[j]return tmpX = [set(),set(),set()]for _ in range(N):s = list(input())[:-1]s = [ord(i)-ord('a')+1 for i in s] + [0]rh = Rolling_hash(s)n = len(s) - 1v0,v1,v2 = rh.query(0,0,n),rh.query(1,0,n),rh.query(2,0,n)if (v0 in X[0])&(v1 in X[1])&(v2 in X[2]):print('Yes')else:print('No')X[0].add(v0)X[1].add(v1)X[2].add(v2)# print(_,v0,v1)for i in range(n-1):flg = 0v0 = (rh.query(flg,0,i)+ rh.query(flg,i,i+1)*rh.b[flg][i+1]+ rh.query(flg,i+1,i+2)*rh.b[flg][i]+ rh.query(flg,i+2,n)*rh.b[flg][i+2])%rh.mod_list[flg]X[0].add(v0)flg = 1v1 = (rh.query(flg,0,i)+ rh.query(flg,i,i+1)*rh.b[flg][i+1]+ rh.query(flg,i+1,i+2)*rh.b[flg][i]+ rh.query(flg,i+2,n)*rh.b[flg][i+2])%rh.mod_list[flg]X[1].add(v1)flg = 2v2 = (rh.query(flg,0,i)+ rh.query(flg,i,i+1)*rh.b[flg][i+1]+ rh.query(flg,i+1,i+2)*rh.b[flg][i]+ rh.query(flg,i+2,n)*rh.b[flg][i+2])%rh.mod_list[flg]X[2].add(v2)# print(i,v0,v1)# print(s)