結果

問題 No.599 回文かい
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:15:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,489 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 86,732 KB
最終ジャッジ日時 2025-05-14 13:17:26
合計ジャッジ時間 10,642 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set higher recursion depth for potentially deep recursive calls.
# The maximum depth could be N/2. For N=10000, this is 5000.
# Add some buffer, e.g., 5010.
try:
    sys.setrecursionlimit(5000 + 10) 
except OverflowError: # Handle cases where the system limit is lower
    pass

# The required modulus for the final answer
MOD = 1_000_000_007 

# Use two different hash parameters for robustness against collisions.
# Hash Function 1 Parameters
P1 = 31  # A common prime base for hashing strings
MOD1 = 1_000_000_007 # Use the same modulus as the final answer is convenient
P_pow1 = [1] * (10001) # Precompute powers of P1 modulo MOD1
for i in range(1, 10001):
    P_pow1[i] = (P_pow1[i-1] * P1) % MOD1

# Hash Function 2 Parameters
P2 = 37  # Another prime base
MOD2 = 1_000_000_009 # A different large prime modulus
P_pow2 = [1] * (10001) # Precompute powers of P2 modulo MOD2
for i in range(1, 10001):
    P_pow2[i] = (P_pow2[i-1] * P2) % MOD2

# Global storage for hash prefix sums and memoization table.
# These will be initialized in the solve() function.
hash_s1 = []
hash_s2 = []
memo = {}

# Function to compute the hash pair for a substring S[l..r-1] (Python slice S[l:r])
# Uses the precomputed prefix hash sums and powers.
def get_hash_pair(l, r):
    # Check for empty substring
    if l >= r:
        return (0, 0)
    
    # Calculate hash value using the first hash function
    # hash_s1[k] stores the hash of prefix S[0..k-1]
    # Hash of S[l..r-1] = hash(S[0..r-1]) - hash(S[0..l-1]) * P^(r-l)
    val1 = (hash_s1[r] - hash_s1[l] * P_pow1[r-l]) % MOD1
    # Adjust if the result is negative due to modulo arithmetic
    if val1 < 0: val1 += MOD1
    
    # Calculate hash value using the second hash function
    val2 = (hash_s2[r] - hash_s2[l] * P_pow2[r-l]) % MOD2
    if val2 < 0: val2 += MOD2
    
    # Return the pair of hash values
    return (val1, val2)

# Recursive function to count palindromic decompositions for substring S[i..j]
# Uses memoization to avoid recomputing results for the same subproblems.
def count_palindromic_decompositions(i, j):
    # i, j are 0-based indices representing the substring S[i]...S[j]
    
    # Base Cases:
    # If the interval is invalid (i > j), it represents an empty substring.
    # An empty string can be thought of as having one decomposition (the empty one),
    # which fits the recursive structure where peeling off matching ends leaves an empty middle part.
    if i > j: return 1 
    # A single character string S[i..i] has exactly one decomposition: [S[i]]
    if i == j: return 1 

    # Check if the result for state (i, j) is already memoized
    state = (i, j)
    if state in memo:
        return memo[state]

    # Initialize the total count. Every non-empty substring S[i..j] has at least one decomposition:
    # Taking the whole substring as a single block T_1. This is the k=1 case.
    total = 1
    
    # The length of the current substring S[i..j]
    length = j - i + 1
    
    # Iterate through possible lengths 'l' for the first block T_1 (and thus the last block T_k)
    # 'l' ranges from 1 up to half the length of the substring.
    for l in range(1, length // 2 + 1):
        
        # Compare the prefix of length 'l' (S[i .. i+l-1]) with the suffix of length 'l' (S[j-l+1 .. j])
        
        # Calculate hash pairs for the prefix and suffix
        # Prefix S[i : i+l] uses indices i to i+l-1
        prefix_hash_pair = get_hash_pair(i, i + l)
        
        # Suffix S[j-l+1 : j+1] uses indices j-l+1 to j
        suffix_hash_pair = get_hash_pair(j - l + 1, j + 1) 
        
        # If the prefix and suffix match (checked using hash pairs)
        if prefix_hash_pair == suffix_hash_pair:
            # If they match, it means we found a valid pair T_1 = T_k.
            # We then need to find the number of palindromic decompositions
            # for the inner substring S[i+l .. j-l].
            # We recursively call the function for this inner part.
            inner_count = count_palindromic_decompositions(i + l, j - l)
            
            # Add the count obtained from the inner decomposition to the total count.
            # All calculations are done modulo MOD.
            total = (total + inner_count) % MOD

    # Memoize the result for state (i, j) before returning
    memo[state] = total
    return total

# Main function to handle input, preprocessing, and output
def solve():
    # Make hash arrays and memoization table global to be accessible by helper functions
    global hash_s1, hash_s2, memo
    
    # Read the input string S
    S = sys.stdin.readline().strip()
    N = len(S)

    # Initialize global hash arrays and memoization table for the current test case
    hash_s1 = [0] * (N + 1)
    hash_s2 = [0] * (N + 1)
    memo = {} # Clear memoization table for each new input string

    # Precompute prefix hashes for S using both hash functions
    for k in range(N):
        # Map character 'a'-'z' to integers 1-26
        char_val = ord(S[k]) - ord('a') + 1 
        # Calculate prefix hash for hash function 1
        hash_s1[k+1] = (hash_s1[k] * P1 + char_val) % MOD1
        # Calculate prefix hash for hash function 2
        hash_s2[k+1] = (hash_s2[k] * P2 + char_val) % MOD2

    # Call the recursive function to compute the result for the entire string S[0..N-1]
    result = count_palindromic_decompositions(0, N - 1)
    
    # Print the final result
    print(result)

# Execute the solve function
solve()
0