結果

問題 No.464 PPAP
ユーザー vwxyzvwxyz
提出日時 2024-12-19 23:01:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,167 bytes
コンパイル時間 486 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 155,556 KB
最終ジャッジ日時 2024-12-19 23:01:44
合計ジャッジ時間 18,601 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
60,508 KB
testcase_01 AC 38 ms
53,608 KB
testcase_02 AC 39 ms
54,972 KB
testcase_03 AC 39 ms
53,500 KB
testcase_04 AC 69 ms
73,440 KB
testcase_05 AC 73 ms
73,424 KB
testcase_06 AC 56 ms
67,076 KB
testcase_07 AC 242 ms
76,692 KB
testcase_08 AC 177 ms
76,700 KB
testcase_09 AC 141 ms
77,092 KB
testcase_10 TLE -
testcase_11 AC 1,926 ms
78,684 KB
testcase_12 TLE -
testcase_13 AC 1,626 ms
78,336 KB
testcase_14 AC 1,690 ms
78,380 KB
testcase_15 AC 42 ms
53,224 KB
testcase_16 AC 40 ms
53,200 KB
testcase_17 AC 50 ms
62,020 KB
testcase_18 AC 50 ms
54,444 KB
testcase_19 AC 58 ms
67,232 KB
testcase_20 AC 59 ms
65,984 KB
testcase_21 AC 54 ms
64,556 KB
testcase_22 AC 56 ms
65,116 KB
testcase_23 AC 1,590 ms
77,576 KB
testcase_24 AC 1,600 ms
77,428 KB
testcase_25 AC 1,664 ms
155,556 KB
権限があれば一括ダウンロードができます

ソースコード

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=(1<<61)-1
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