結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:47:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,959 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 88,708 KB
最終ジャッジ日時 2025-05-14 12:49:29
合計ジャッジ時間 4,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**18 + 3
BASE = 911382629

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    if n < 4:
        print(0)
        return
    
    # Precompute is_pal_start
    is_pal_start = [False] * n
    for i in range(n):
        left = 0
        right = i
        valid = True
        while left < right:
            if S[left] != S[right]:
                valid = False
                break
            left += 1
            right -= 1
        is_pal_start[i] = valid
    
    # Precompute is_pal_end
    is_pal_end = [False] * (n + 1)
    for k in range(n):
        left = k
        right = n - 1
        valid = True
        while left < right:
            if S[left] != S[right]:
                valid = False
                break
            left += 1
            right -= 1
        is_pal_end[k] = valid
    is_pal_end[n] = False  # since P3 must be non-empty
    
    # Precompute prefix hash and power for S
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * BASE + ord(S[i])) % MOD
        power[i+1] = (power[i] * BASE) % MOD
    
    # Precompute reversed string's prefix hash
    S_rev = S[::-1]
    prefix_hash_rev = [0] * (n + 1)
    for i in range(n):
        prefix_hash_rev[i+1] = (prefix_hash_rev[i] * BASE + ord(S_rev[i])) % MOD
    
    # Function to get hash of S[a..b]
    def get_hash(a, b):
        if a > b:
            return 0
        res = (prefix_hash[b+1] - prefix_hash[a] * power[b - a + 1]) % MOD
        return res
    
    # Function to get hash of S_rev[a..b]
    def get_hash_rev(a, b):
        if a > b:
            return 0
        res = (prefix_hash_rev[b+1] - prefix_hash_rev[a] * power[b - a + 1]) % MOD
        return res
    
    # Precompute cnt[j] for all j
    cnt = [0] * n
    for j in range(n):
        # a can be from 1 to j (i+1 = a, i = a-1)
        for a in range(1, j + 1):
            # Check if a-1 is a palindrome prefix
            if not is_pal_start[a-1]:
                continue
            # Check if a..j is a palindrome
            len_sub = j - a + 1
            rev_a = n - 1 - j
            rev_b = n - 1 - a
            hash_sub = get_hash(a, j)
            hash_rev_sub = get_hash_rev(rev_a, rev_b)
            if hash_sub == hash_rev_sub:
                cnt[j] += 1
    
    # Compute prefix sum of cnt
    prefix_cnt = [0] * (n + 1)
    for i in range(n):
        prefix_cnt[i+1] = prefix_cnt[i] + cnt[i]
    
    # Compute suffix count of is_pal_end
    suffix_pal = [0] * (n + 2)  # suffix_pal[k] = number of k' >=k where is_pal_end[k'] is true
    for k in range(n-1, -1, -1):
        suffix_pal[k] = suffix_pal[k+1] + (1 if is_pal_end[k] else 0)
    
    # Compute the answer
    ans = 0
    for j in range(n):
        k_min = j + 2
        if k_min >= n:
            continue
        ans += cnt[j] * suffix_pal[k_min]
    
    print(ans)

if __name__ == "__main__":
    main()
0