結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def count_palindrome_decompositions(S):
    n = len(S)
    if n == 0:
        return 0
    
    # Precompute prefix hashes and power array
    base = 911382629
    mod = 10**18 + 3
    
    prefix = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = (prefix[i-1] * base + ord(S[i-1])) % mod
        power[i] = (power[i-1] * base) % mod
    
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty string has one decomposition
    
    for i in range(1, n + 1):
        dp[i] = 1  # The case where the entire string is one part
        
        max_j = i // 2
        for j in range(1, max_j + 1):
            # Compute hash of S[0:j]
            a = 0
            b = j
            h1 = (prefix[b] - prefix[a] * power[b - a]) % mod
            
            # Compute hash of S[i-j:i]
            c = i - j
            d = i
            h2 = (prefix[d] - prefix[c] * power[d - c]) % mod
            
            if h1 == h2:
                prev = i - 2 * j
                if prev >= 0:
                    dp[i] = (dp[i] + dp[prev]) % MOD
    
    return dp[n] % MOD

# Read input and output the result
S = input().strip()
print(count_palindrome_decompositions(S))
0