結果

問題 No.464 PPAP
ユーザー vwxyz
提出日時 2024-12-19 23:05:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 538 ms / 2,000 ms
コード長 2,165 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 78,028 KB
最終ジャッジ日時 2024-12-19 23:05:51
合計ジャッジ時間 6,014 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Rolling_Hash:
    def __init__(self,lst,base,mod=0,e_sum=0,e_prod=1):
        self.len=len(lst)
        self.base=base
        self.mod=mod
        self.e_sum=e_sum
        self.e_prod=e_prod
        self.rolling_hash=[lst[i] for i in range(self.len)]+[self.e_sum]
        self.pow_base=[self.e_prod]
        for i in range(self.len-1,-1,-1):
            self.rolling_hash[i]+=self.rolling_hash[i+1]*self.base
            self.pow_base.append(self.pow_base[-1]*self.base)
            if self.mod:
                self.rolling_hash[i]%=self.mod
                self.pow_base[-1]%=self.mod

    def Build_Pow(self,N):
        while len(self.pow_base)<N+1:
            self.pow_base.append(self.pow_base[-1]*self.base)
            if self.mod:
                self.pow_base[-1]%=self.mod

    def __getitem__(self,i):
        if type(i)==int:
            a,b=i,i+1
        else:
            a,b=i.start,i.stop
            if a==None or a<-self.len:
                a=0
            elif self.len<=a:
                a=self.len
            elif a<0:
                a+=self.len
            if b==None or self.len<=b:
                b=self.len
            elif b<-self.len:
                b=0
            elif b<0:
                b+=self.len
        h=self.rolling_hash[a]-self.rolling_hash[b]*self.pow_base[b-a]
        if self.mod:
            h%=self.mod
        return (h,b-a)
    
    def concat(self,hash0,hash1):
        h0,le0=hash0
        h1,le1=hash1
        if le0<len(self.pow_base):
            h=h0+h1*self.pow_base[le0]
        else:
            h=h0+h1*(pow(self.base,le0,self.mod) if self.mod else pow(self.base,le0))
        if self.mod:
            h%=self.mod
        le=le0+le1
        return (h,le)

    def __len__(self):
        return self.len

S=input()
mod=10**9+7
RH0=Rolling_Hash([ord(s) for s in S],base=100,mod=mod)
RH1=Rolling_Hash([ord(s) for s in S[::-1]],base=100,mod=mod)
N=len(S)
ans=0
cnt=0
def palindrome(i,j):
    return RH0[i:j]==RH1[N-j:N-i]
for j in range(N-2,-1,-1):
    if palindrome(j+1,N):
        cnt+=1
    for i in range(j-1,0,-1):
        if palindrome(0,i) and palindrome(i,j):
            ans+=cnt
print(ans)
0