結果
問題 |
No.599 回文かい
|
ユーザー |
|
提出日時 | 2025-08-09 14:07:17 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 742 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 375,636 KB |
最終ジャッジ日時 | 2025-08-09 14:07:28 |
合計ジャッジ時間 | 9,031 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 MLE * 2 |
ソースコード
S = list(map(lambda x:ord(x), input())) 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) 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)