結果

問題 No.599 回文かい
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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])
0