結果

問題 No.599 回文かい
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:38:41
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,912 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 454,016 KB
最終ジャッジ日時 2025-03-31 17:39:54
合計ジャッジ時間 11,231 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 MLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    if n == 0:
        print(0)
        return
    
    # Precompute base powers for rolling hash
    base = 911382487
    mod = 10**18 + 3
    
    prefix = [0] * (n + 1)
    pow_base = [1] * (n + 1)
    for i in range(n):
        prefix[i+1] = (prefix[i] * base + ord(S[i])) % mod
        pow_base[i+1] = (pow_base[i] * base) % mod
    
    # Compute hash for reverse string
    reversed_S = S[::-1]
    prefix_rev = [0] * (n + 1)
    for i in range(n):
        prefix_rev[i+1] = (prefix_rev[i] * base + ord(reversed_S[i])) % mod
    
    # Function to get hash of s[l..r]
    def get_hash(prefix, l, r):
        res = (prefix[r+1] - prefix[l] * pow_base[r - l + 1]) % mod
        return res
    
    dp = [[0] * n for _ in range(n)]
    
    # Precompute lengths in increasing order
    for length in range(1, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if i == j:
                dp[i][j] = 1
                continue
            res = 1  # Case k=1, split into one part
            max_l = (length) // 2
            for l in range(1, max_l + 1):
                # Check if left and right parts are equal
                left_i, left_j = i, i + l - 1
                right_i, right_j = j - l + 1, j
                hash_left = get_hash(prefix, left_i, left_j)
                hash_right = get_hash(prefix, right_i, right_j)
                if hash_left == hash_right:
                    next_i = i + l
                    next_j = j - l
                    if next_i <= next_j:
                        res += dp[next_i][next_j]
                    else:
                        res += 1  # The middle part is empty, count as 1 way
                    res %= MOD
            dp[i][j] = res % MOD
    
    print(dp[0][n-1] % MOD)

if __name__ == "__main__":
    main()
0