結果

問題 No.464 PPAP
ユーザー lam6er
提出日時 2025-03-20 20:25:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 863 ms / 2,000 ms
コード長 1,039 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 272,448 KB
最終ジャッジ日時 2025-03-20 20:27:01
合計ジャッジ時間 8,298 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

s = input().strip()
n = len(s)
if n < 4:
    print(0)
    exit()

# 预处理回文数组
pal = [[False] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(i, n):
        if i == j:
            pal[i][j] = True
        elif j == i + 1:
            pal[i][j] = (s[i] == s[j])
        else:
            pal[i][j] = (s[i] == s[j]) and pal[i+1][j-1]

# 预处理每个k是否为回文后缀
right_pal = [False] * n
for k in range(n):
    right_pal[k] = pal[k][n-1]

# 预处理前缀和数组
pre_sum = [0] * (n + 1)
pre_sum[n] = 0
for k in range(n-1, -1, -1):
    pre_sum[k] = pre_sum[k+1] + (1 if right_pal[k] else 0)

ans = 0

# 遍历所有可能的i和j的组合
for i in range(n-3):
    if not pal[0][i]:
        continue
    max_j = n - 3
    # j的范围是i+1到max_j
    for j in range(i + 1, max_j + 1):
        if not pal[i+1][j]:
            continue
        start_k = j + 2
        end_k = n - 1
        if start_k > end_k:
            continue
        ans += pre_sum[start_k] - pre_sum[end_k + 1]

print(ans)
0