Cho mảng nums kích thước n và mảng queries các cặp (p_i, q_i). Với mỗi query, tính tổng nums[j] với p_i ≤ j < n và (j - p_i) chia hết cho q_i. Trả về mảng kết quả modulo 10⁹+7.
Ví dụ: nums = [2,3,4,5,6,7,8,9,10], queries = [(2,5),(7,3),(6,4)] → output = [13,9,8].
Giải thuật (Sqrt decomposition / Precompute cho step nhỏ)
- m = √n + 2.
- Precompute P[k][j] = sum nums[j] + nums[j+k] + nums[j+2k] + ... cho mọi k < m.
- Query (b,k): nếu k < m → trả P[k][b]; ngược lại duyệt trực tiếp (số bước ≤ √n).
Code Python
def solve(A, Q):
n, M = len(A), 10**9 + 7
m = int(n**0.5) + 2
P = [A[:] for _ in range(m)]
for i in range(1, m):
for j in range(n - 1, -1, -1):
if i + j < n:
P[i][j] = (P[i][j] + P[i][i + j]) % M
return [P[k][b] if k < m else sum(A[b::k]) % M for b, k in Q]
print(solve([2,3,4,5,6,7,8,9,10], [(2,5),(7,3),(6,4)])) # [13, 9, 8]
Đầu vào / Đầu ra
Input: [2,3,4,5,6,7,8,9,10], [(2,5),(7,3),(6,4)]
Output: [13, 9, 8]