結果

問題 No.599 回文かい
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:51:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,194 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 76,684 KB
最終ジャッジ日時 2025-06-12 16:52:34
合計ジャッジ時間 19,061 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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