結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:03:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,105 bytes
コンパイル時間 769 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 108,116 KB
最終ジャッジ日時 2025-04-09 21:05:59
合計ジャッジ時間 5,693 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    s = sys.stdin.readline().strip()
    n = len(s)
    if n < 4:
        print(0)
        return

    MOD = 10**18 + 3
    BASE = 911382629

    # Precompute forward hash and power
    forward_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        forward_hash[i+1] = (forward_hash[i] * BASE + ord(s[i])) % MOD
        power[i+1] = (power[i] * BASE) % MOD

    # Precompute reverse hash and power for the reversed string
    reversed_s = s[::-1]
    reverse_hash = [0] * (n + 1)
    for i in range(n):
        reverse_hash[i+1] = (reverse_hash[i] * BASE + ord(reversed_s[i])) % MOD

    def get_hash(h, l, r):
        return (h[r] - h[l] * power[r - l]) % MOD

    def is_palindrome(l, r):
        if l >= r:
            return False
        rev_l = n - r
        rev_r = rev_l + (r - l)
        forward = get_hash(forward_hash, l, r)
        reverse = get_hash(reverse_hash, rev_l, rev_r)
        return forward == reverse

    # Precompute P1_possible: whether S[0..i-1] is a palindrome
    P1_possible = [False] * (n + 1)
    for i in range(1, n + 1):
        P1_possible[i] = is_palindrome(0, i)

    # Precompute P3_possible and sum_p3
    P3_possible = [False] * (n + 1)
    for k in range(n):
        if is_palindrome(k, n):
            P3_possible[k] = True

    sum_p3 = [0] * (n + 2)
    for k in range(n-1, -1, -1):
        sum_p3[k] = sum_p3[k + 1] + (1 if P3_possible[k] else 0)

    answer = 0

    # Iterate all possible i (end of P1)
    for i in range(1, n - 2 + 1):  # i can be up to n-3, since j needs to be at least i+1, and k >=j+1 needs to be valid
        if not P1_possible[i]:
            continue

        # Iterate possible j (end of P2)
        # j must be i+1 <= j <=n-2, and [i..j-1] must be a palindrome
        max_j = n - 2  # because k needs to be >= j+1 and <=n-1
        for j in range(i + 1, max_j + 1):
            if not is_palindrome(i, j):
                continue
            # sum_p3[j+1] is the number of valid k >= j+1
            answer += sum_p3[j + 1]

    print(answer)

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