結果

問題 No.599 回文かい
ユーザー lam6er
提出日時 2025-04-15 23:31:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,144 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 76,772 KB
最終ジャッジ日時 2025-04-15 23:33:08
合計ジャッジ時間 16,486 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7
base = 911382629
mod = 10**18 + 3

s = input().strip()
n = len(s)

if n == 0:
    print(0)
else:
    # Precompute prefix hashes and power of base
    prefix_hash = [0] * (n + 1)
    pow_base = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + ord(s[i])) % mod
        pow_base[i+1] = (pow_base[i] * base) % mod

    def get_hash(l, r):
        # Returns hash of s[l..r] (0-based, inclusive)
        length = r - l + 1
        res = (prefix_hash[r+1] - prefix_hash[l] * pow_base[length]) % mod
        return res

    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 substring is not split
        max_m = i // 2
        for m in range(1, max_m + 1):
            if i - 2 * m < 0:
                continue
            # Check if the first m characters and last m characters are equal
            hash_front = get_hash(0, m-1)
            hash_back = get_hash(i - m, i - 1)
            if hash_front == hash_back:
                dp[i] = (dp[i] + dp[i - 2 * m]) % MOD

    print(dp[n] % MOD)
0