結果

問題 No.599 回文かい
ユーザー 前田悠真
提出日時 2025-08-09 14:11:58
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 588 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 371,456 KB
最終ジャッジ日時 2025-08-09 14:12:04
合計ジャッジ時間 5,053 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 20 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #

S = list(map(lambda x:ord(x), input()))

n = len(S)
if n==1:
  print(1)
  exit()
mod = 10**9+7

p = 1007
mod2 = mod


G = [set() for _ in range(n//2+1)]
dp = [0]*(n//2+1)

# print(SR)
pp = pow(p, mod2-2, mod2)
for i in range(n//2):
  left = 0
  right = 0
  p_ = 1
  for j in range(i, n//2):
    left += p_*S[j]
    left %= mod
    right = right*p+S[~j]
    right %= mod
    p_ *= p
    p_ %= mod
    if left==right:
      G[i].add(j+1)


# print(G)

dp[0] = 1

ans = 0
for i in range(n//2+1):
  ans += dp[i]
  ans %= mod
  for v in G[i]:
    dp[v] += dp[i]
    dp[v] %= mod

print(ans)


0