結果

問題 No.599 回文かい
コンテスト
ユーザー 前田悠真
提出日時 2025-08-09 14:06:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 774 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 375,040 KB
最終ジャッジ日時 2025-08-09 14:06:51
合計ジャッジ時間 10,622 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

S = list(map(lambda x:ord(x), input()))
S_ = S[::-1]
n = len(S)
if n==1:
  print(1)
  exit()
mod = 10**9+7

p = 1007
mod2 = 2222222227727
def transform(S):
  A = [0]*n
  t = 0
  p_ = 1
  for i, s in enumerate(S):
    t += p_*s
    t %= mod2
    A[i] = t
    p_ *= p
    p_ %= mod2
  return A

SR = transform(S)
SR_ = transform(S_)

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):
  x = pow(pp, n-1-2*i, mod2)
  for j in range(i, n//2):
    if (SR[j]-(SR[i-1] if i-1>=0 else 0))%mod2==(SR[~i]-SR[~(j+1)])*x%mod2:
      G[i].add(j+1)
    x *= p
    x %= mod2

# 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