結果
| 問題 |
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 |
ソースコード
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()