結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:47:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,598 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 81,676 KB
実行使用メモリ 250,372 KB
最終ジャッジ日時 2025-05-14 12:48:15
合計ジャッジ時間 5,575 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    if n < 4:
        print(0)
        return
    
    # Precompute prefix_hash and reverse_hash for palindrome checks
    base = 911382629
    mod = 10**18 + 3
    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
    
    reverse_hash = [0] * (n + 1)
    reversed_S = S[::-1]
    for i in range(n):
        reverse_hash[i+1] = (reverse_hash[i] * base + ord(reversed_S[i])) % mod
    
    def get_hash(s, e):
        if s > e:
            return 0
        res = (prefix_hash[e+1] - prefix_hash[s] * power[e+1 - s]) % mod
        return res if res >= 0 else res + mod
    
    def get_rev_hash(s, e):
        rev_s = n - 1 - e
        rev_e = n - 1 - s
        res = (reverse_hash[rev_e + 1] - reverse_hash[rev_s] * power[rev_e + 1 - rev_s]) % mod
        return res if res >= 0 else res + mod
    
    # Precompute is_prefix_palin
    is_prefix_palin = [False] * n
    for i in range(n):
        if get_hash(0, i) == get_rev_hash(0, i):
            is_prefix_palin[i] = True
    
    # Precompute is_palin_end and sum_palin_end
    is_palin_end = [False] * n
    for k in range(n):
        if get_hash(k, n-1) == get_rev_hash(k, n-1):
            is_palin_end[k] = True
    
    sum_palin_end = [0] * (n + 2)
    for j in range(n-1, -1, -1):
        sum_palin_end[j] = sum_palin_end[j+1] + (1 if is_palin_end[j] else 0)
    
    # Build Eertree and current_nodes
    class EertreeNode:
        __slots__ = ['length', 'suffix_link', 'transitions']
        def __init__(self, length, suffix_link):
            self.length = length
            self.suffix_link = suffix_link
            self.transitions = {}
    
    root_neg1 = EertreeNode(-1, None)
    root_0 = EertreeNode(0, root_neg1)
    root_neg1.suffix_link = root_neg1
    tree = [root_neg1, root_0]
    current = root_0
    current_nodes = []
    for i, c in enumerate(S):
        prev = current
        while True:
            if i - prev.length - 1 >= 0 and S[i - prev.length - 1] == c:
                break
            prev = prev.suffix_link
        if c in prev.transitions:
            current = prev.transitions[c]
        else:
            new_node = EertreeNode(prev.length + 2, None)
            tree.append(new_node)
            prev.transitions[c] = new_node
            if new_node.length == 1:
                new_node.suffix_link = root_0
            else:
                suffix_link = prev.suffix_link
                while True:
                    if i - suffix_link.length - 1 >= 0 and S[i - suffix_link.length - 1] == c:
                        break
                    suffix_link = suffix_link.suffix_link
                new_node.suffix_link = suffix_link.transitions.get(c, root_0)
            current = new_node
        current_nodes.append(current)
    
    # Compute count_i[j]
    count_i = [0] * n
    for j in range(n):
        current_node = current_nodes[j]
        while current_node.length > 0:
            length = current_node.length
            s = j - length + 1
            if s >= 0:
                if s - 1 >= 0 and is_prefix_palin[s - 1]:
                    count_i[j] += 1
            current_node = current_node.suffix_link
    
    # Calculate the answer
    ans = 0
    for j in range(n):
        k_start = j + 2
        if k_start >= n:
            continue
        ans += count_i[j] * sum_palin_end[k_start]
    
    print(ans)

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