結果

問題 No.1172 Add Recursive Sequence
ユーザー qwewe
提出日時 2025-05-14 13:20:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 8,459 bytes
コンパイル時間 422 ms
コンパイル使用メモリ 82,896 KB
実行使用メモリ 89,300 KB
最終ジャッジ日時 2025-05-14 13:22:28
合計ジャッジ時間 9,310 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 14 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

# Set higher recursion depth for deep calculations if needed, though not expected for this problem
# sys.setrecursionlimit(2000) 

# Using naive O(K^2) polynomial multiplication. 
# This part is the bottleneck and needs replacement with NTT (Number Theoretic Transform) 
# based polynomial multiplication for the given constraints to pass within the time limit.
# The provided solution structure is correct, but performance depends on this function.
def multiply_naive(P, Q, K, mod):
    """
    Computes the first K coefficients of the product P(z) * Q(z) modulo mod.
    P: list representing polynomial P(z), P[k] is coefficient of z^k.
    Q: list representing polynomial Q(z), Q[k] is coefficient of z^k.
    K: number of coefficients needed (coefficients for z^0 to z^{K-1}).
    mod: modulus for calculations.
    """
    res = [0] * K
    degP = len(P)
    degQ = len(Q)
    
    # Iterate through terms of P
    for i in range(degP):
        if P[i] == 0: continue # Optimization: skip if coefficient is zero
        Pi = P[i] 
        
        # Iterate through terms of Q
        for j in range(degQ):
            # Optimization: skip if coefficient is zero
            if Q[j] == 0: continue 
            
            # Compute the degree of the resulting term
            term_deg = i + j
            
            # If the term degree is within the required range [0, K-1]
            if term_deg < K:
                # Calculate the product of coefficients modulo mod
                # Perform multiplication only if term contributes to result
                term = (Pi * Q[j]) % mod
                # Add to the corresponding coefficient in the result polynomial
                res[term_deg] = (res[term_deg] + term) % mod
    return res

def solve():
    # Read input: K, N, M
    K, N, M = map(int, sys.stdin.readline().split())
    
    # Read initial values of sequence a
    A = list(map(int, sys.stdin.readline().split()))
    
    # Read coefficients c_k
    C_input = list(map(int, sys.stdin.readline().split()))
    
    MOD = 10**9 + 7

    # Store coefficients c_k in a 1-indexed list for convenience
    C = [0] * (K + 1) 
    for i in range(K):
        C[i+1] = C_input[i]

    # Precompute sequence `a` terms up to N+K-1. We need indices up to N+K-2.
    # Max index needed is related to r_j+p-k-l_j, which can be N+K-2 when r_j=N, l_j=0, p=K-1, k=1.
    a = [0] * (N + K)
    for i in range(K):
        a[i] = A[i]

    # Compute terms a_K, ..., a_{N+K-1} using the recurrence relation
    for i in range(K, N + K):
        val = 0
        for k in range(1, K + 1):
            # Check index bounds: i-k must be non-negative
            if i - k >= 0:
                # Add c_k * a_{i-k} to the current value
                val = (val + C[k] * a[i - k]) % MOD
        a[i] = val

    # Create a padded version of `a` with K zeros at the beginning. 
    # This allows accessing a_{idx} using index K+idx, handling negative indices implicitly returning 0.
    # The total size is K (padding) + N + K (values) = N + 2K.
    a_neg_padded = [0]*K + a 

    # Precompute B_p values for p = 0 to K-1.
    # B_p = a_p - sum_{k=1..p} c_k a_{p-k}
    B = [0] * K
    for p in range(K):
        sum_term = 0
        # Calculate the sum part
        for k in range(1, p + 1):
             # Access a_{p-k} using padded index K + p - k
             sum_term = (sum_term + C[k] * a_neg_padded[K + p - k]) % MOD 
        # Compute B_p = (a_p - sum_term) mod MOD
        B[p] = (a[p] - sum_term + MOD) % MOD
    
    # Precompute delta_p values for p = 0 to K-1.
    # delta_p = a_p - sum_{k=1..K} c_k a_{p-k}
    delta = [0] * K
    for p in range(K):
         sum_term = 0
         # Calculate the sum part
         for k in range(1, K+1):
             # Access a_{p-k} using padded index K + p - k
             sum_term = (sum_term + C[k] * a_neg_padded[K + p - k]) % MOD
         # Compute delta_p = (a_p - sum_term) mod MOD
         delta[p] = (a[p] - sum_term + MOD) % MOD

    # Initialize the difference array D for X_i recurrence
    # D will store the adjustments needed at each step i. Size N is sufficient.
    D = [0] * N 

    # Prepare the polynomial C(z) = c_1 z + ... + c_K z^K
    # Represented as a list [0, c1, c2, ..., cK] where C_poly[k] is coeff of z^k.
    C_poly = [0] * (K+1)
    for k in range(1, K+1):
      C_poly[k] = C[k]
    
    # Preallocate list for A_idx(z) polynomial to avoid reallocations inside the loop
    A_idx_poly = [0] * K

    # Process M operations
    for _ in range(M):
        # Read operation parameters l_j, r_j
        l, r = map(int, sys.stdin.readline().split())
        # Calculate the index difference: idx = r_j - l_j
        idx = r - l

        # Prepare the polynomial A_idx(z) = a_idx + a_{idx+1} z + ... + a_{idx+K-1} z^{K-1}
        # Represented as list [a_idx, a_{idx+1}, ..., a_{idx+K-1}]
        for p in range(K):
             # Need a_{idx+p}. Access using padded index K+idx+p
             # Check array bounds: valid index range is [0, N+2K-1] for a_neg_padded
             padded_idx = K + idx + p
             if padded_idx < len(a_neg_padded):
                 A_idx_poly[p] = a_neg_padded[padded_idx]
             else: # If index is out of bounds, the term a_{idx+p} is considered 0
                 A_idx_poly[p] = 0 

        # Compute S_{j,p} values using polynomial multiplication.
        # S_p_list[p] = coefficient of z^p in C(z) * A_idx(z) mod z^K.
        # This is the performance critical step. multiply_naive is O(K^2).
        S_p_list = multiply_naive(C_poly, A_idx_poly, K, MOD) 

        # Compute E_{j,p} values list for the current operation j.
        E_p_list = [0] * K
        for p in range(K):
            # The index in sequence 'a' we are interested in is idx+p
            target_a_idx = idx + p
            target_a_val = 0
            # Access a_{idx+p} using padded index K + idx + p
            # Check index bounds and ensure we access non-negative indices in original 'a' sequence
            padded_idx = K + target_a_idx
            if padded_idx < len(a_neg_padded) and padded_idx >= K: 
                 target_a_val = a_neg_padded[padded_idx]

            # Get the precomputed S_{j,p} value
            S_p_val = S_p_list[p]

            # Calculate E_{j,p} based on whether idx+p < K
            if target_a_idx < K:
                current_delta_p = 0
                # delta_p is defined for p=0..K-1. Check target_a_idx >= 0
                if target_a_idx >= 0: 
                   current_delta_p = delta[target_a_idx]
                
                # E_p = -(a_{idx+p} - delta_{idx+p} - S_{j,p}) mod MOD
                term = (target_a_val - current_delta_p - S_p_val) % MOD
                E_p_list[p] = (-term + MOD) % MOD

            else: # target_a_idx >= K
                # E_p = -(a_{idx+p} - S_{j,p}) mod MOD
                term = (target_a_val - S_p_val) % MOD
                E_p_list[p] = (-term + MOD) % MOD

        # Update the difference array D based on B_p and E_{j,p}
        for p in range(K):
            # Update for index l+p: Add B_p if l+p < N and l+p is within range [l, r)
            idx_l_p = l + p
            if idx_l_p < N:
                if idx_l_p < r: # Check if the index is within the update range [l, r)
                    D[idx_l_p] = (D[idx_l_p] + B[p]) % MOD
            
            # Update for index r+p: Add E_{j,p} if r+p < N
            idx_r_p = r + p
            if idx_r_p < N:
                 D[idx_r_p] = (D[idx_r_p] + E_p_list[p]) % MOD

    # Compute the final X values using the recurrence X_i = sum_{k=1..K} c_k X_{i-k} + D_i
    X = [0] * N
    # Use a padded version of X for calculation ease: K zeros prefix. Size K+N.
    X_padded = [0]*K + [0]*N 
    
    for i in range(N):
        sum_term = 0
        # Calculate the sum part of the recurrence
        for k in range(1, K + 1):
             # Access X_{i-k} using padded index K + i - k
             sum_term = (sum_term + C[k] * X_padded[K + i - k]) % MOD
        
        # Compute X_i = (sum_term + D_i) mod MOD
        X_padded[K+i] = (sum_term + D[i]) % MOD
        # Store the final value in X[i]
        X[i] = X_padded[K+i]

    # Output the results
    # Use sys.stdout.write for potentially faster output in competitive programming
    output_lines = []
    for val in X:
        output_lines.append(str(val))
    
    sys.stdout.write("\n".join(output_lines) + "\n")

solve()
0