結果
問題 |
No.599 回文かい
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:25:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,194 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 76,248 KB |
最終ジャッジ日時 | 2025-06-12 21:26:06 |
合計ジャッジ時間 | 18,047 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 15 |
ソースコード
MOD = 10**9 + 7 def count_palindromic_decompositions(S): n = len(S) if n == 0: return 0 base = 911382629 mod_hash = 10**18 + 3 prefix_hash = [0] * (n + 1) power = [1] * (n + 1) for i in range(n): prefix_hash[i+1] = (prefix_hash[i] * base + ord(S[i])) % mod_hash power[i+1] = (power[i] * base) % mod_hash dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): dp[i] = 1 # The decomposition with the entire substring as one part max_k = i // 2 for k in range(1, max_k + 1): # Compute hash of first k characters hash_first = prefix_hash[k] # Compute hash of last k characters of the first i characters hash_last = (prefix_hash[i] - prefix_hash[i - k] * power[k]) % mod_hash hash_last = hash_last % mod_hash # Ensure it's positive if hash_first == hash_last: remaining_length = i - 2 * k if remaining_length >= 0: dp[i] = (dp[i] + dp[remaining_length]) % MOD return dp[n] % MOD # Read input S = input().strip() print(count_palindromic_decompositions(S))