結果

問題 No.1994 Confusing Name
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-08-25 20:45:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 489 ms / 2,000 ms
コード長 1,128 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 142,552 KB
最終ジャッジ日時 2024-08-25 20:45:33
合計ジャッジ時間 8,978 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

n=int(input())
ss=[]
d={}
B1=1007
M1=1000000007
P1=[1]
for i in range(1,10):
P1+=[P1[-1]*B1%M1]
B2=1009
M2=1000000009
P2=[1]
for i in range(1,10):
P2+=[P2[-1]*B2%M2]
for i in range(n):
s=input()
h1=0
h2=0
for j in range(len(s)):
h1+=ord(s[j])*P1[j]
h1%=M1
h2+=ord(s[j])*P2[j]
h2%=M2
h=(h1,h2)
if h not in d:
d[h]=0
d[h]+=1
for j in range(len(s)):
h1-=ord(s[j])*P1[j]
h1+=ord("?")*P1[j]
h1%=M1
h2-=ord(s[j])*P2[j]
h2+=ord("?")*P2[j]
h2%=M2
h=(h1,h2)
if h not in d:
d[h]=0
d[h]+=1
h1-=ord("?")*P1[j]
h1+=ord(s[j])*P1[j]
h1%=M1
h2-=ord("?")*P2[j]
h2+=ord(s[j])*P2[j]
h2%=M2
ss+=[s]
for i in range(n):
s=ss[i]
h1=0
h2=0
for j in range(len(s)):
h1+=ord(s[j])*P1[j]
h1%=M1
h2+=ord(s[j])*P2[j]
h2%=M2
c=0
for j in range(len(s)):
h1-=ord(s[j])*P1[j]
h1+=ord("?")*P1[j]
h1%=M1
h2-=ord(s[j])*P2[j]
h2+=ord("?")*P2[j]
h2%=M2
h=(h1,h2)
c+=d[h]-1
h1-=ord("?")*P1[j]
h1+=ord(s[j])*P1[j]
h1%=M1
h2-=ord("?")*P2[j]
h2+=ord(s[j])*P2[j]
h2%=M2
print(c)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0