結果
問題 |
No.599 回文かい
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:22:17 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,582 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 76,872 KB |
最終ジャッジ日時 | 2025-06-12 15:22:37 |
合計ジャッジ時間 | 17,007 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 WA * 9 TLE * 2 -- * 6 |
ソースコード
MOD = 10**9 + 7 def count_palindrome_decompositions(s): n = len(s) if n == 0: return 0 # Precompute hashes using two bases to avoid collision base1 = 911382629 base2 = 3571428571 mod1 = 10**18 + 3 mod2 = 10**18 + 7 prefix_hash1 = [0] * (n + 1) prefix_hash2 = [0] * (n + 1) power1 = [1] * (n + 1) power2 = [1] * (n + 1) for i in range(n): prefix_hash1[i+1] = (prefix_hash1[i] * base1 + ord(s[i])) % mod1 prefix_hash2[i+1] = (prefix_hash2[i] * base2 + ord(s[i])) % mod2 power1[i+1] = (power1[i] * base1) % mod1 power2[i+1] = (power2[i] * base2) % mod2 def get_hash1(l, r): # [l, r) 0-based res = (prefix_hash1[r] - prefix_hash1[l] * power1[r - l]) % mod1 return res if res >= 0 else res + mod1 def get_hash2(l, r): res = (prefix_hash2[r] - prefix_hash2[l] * power2[r - l]) % mod2 return res if res >= 0 else res + mod2 dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): total = 0 max_j = i // 2 for j in range(1, max_j + 1): l1, r1 = 0, j l2, r2 = i - j, i h1_1 = get_hash1(l1, r1) h2_1 = get_hash2(l1, r1) h1_2 = get_hash1(l2, r2) h2_2 = get_hash2(l2, r2) if h1_1 == h1_2 and h2_1 == h2_2: total += dp[i - 2 * j] if total >= MOD: total -= MOD dp[i] = (total + 1) % MOD return dp[n] % MOD s = input().strip() print(count_palindrome_decompositions(s))