結果
問題 |
No.1172 Add Recursive Sequence
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()