結果
問題 |
No.599 回文かい
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:21:48 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,211 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 81,616 KB |
実行使用メモリ | 76,356 KB |
最終ジャッジ日時 | 2025-06-12 20:22:26 |
合計ジャッジ時間 | 18,410 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 15 |
ソースコード
MOD = 10**9 + 7 def count_palindrome_decompositions(S): n = len(S) if n == 0: return 0 # Precompute prefix hashes and power array base = 911382629 mod = 10**18 + 3 prefix = [0] * (n + 1) power = [1] * (n + 1) for i in range(1, n + 1): prefix[i] = (prefix[i-1] * base + ord(S[i-1])) % mod power[i] = (power[i-1] * base) % mod dp = [0] * (n + 1) dp[0] = 1 # Empty string has one decomposition for i in range(1, n + 1): dp[i] = 1 # The case where the entire string is one part max_j = i // 2 for j in range(1, max_j + 1): # Compute hash of S[0:j] a = 0 b = j h1 = (prefix[b] - prefix[a] * power[b - a]) % mod # Compute hash of S[i-j:i] c = i - j d = i h2 = (prefix[d] - prefix[c] * power[d - c]) % mod if h1 == h2: prev = i - 2 * j if prev >= 0: dp[i] = (dp[i] + dp[prev]) % MOD return dp[n] % MOD # Read input and output the result S = input().strip() print(count_palindrome_decompositions(S))