結果
問題 |
No.599 回文かい
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:28:00 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,230 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 76,756 KB |
最終ジャッジ日時 | 2025-03-20 20:29:25 |
合計ジャッジ時間 | 18,648 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 15 |
ソースコード
S = input().strip() n = len(S) mod_answer = 10**9 + 7 base = 911382629 hash_mod = 10**18 + 3 # Precompute powers of the base pow_base = [1] * (n + 1) for i in range(1, n + 1): pow_base[i] = (pow_base[i-1] * base) % hash_mod # Precompute prefix hashes prefix_hash = [0] * (n + 1) for i in range(n): prefix_hash[i + 1] = (prefix_hash[i] * base + ord(S[i])) % hash_mod # Initialize DP array dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): current = 1 # Case when k=1 (no split) max_l = i // 2 for l in range(1, max_l + 1): # Calculate hash of the first l characters hash_first = prefix_hash[l] # Calculate hash of the last l characters of the current i-length substring end = i start = end - l # Compute the hash using prefix_hash and pow_base hash_last = (prefix_hash[end] - prefix_hash[start] * pow_base[l]) % hash_mod hash_last = (hash_last + hash_mod) % hash_mod # Ensure non-negative if hash_first == hash_last: remaining_length = i - 2 * l if remaining_length >= 0: current += dp[remaining_length] current %= mod_answer dp[i] = current % mod_answer print(dp[n])