Giả sử, có một mảng 'nums' kích thước n chứa các số nguyên dương. Chúng ta có một mảng 'truy vấn' khác chứa các cặp số nguyên (pi, qi). Đối với mọi truy vấn trong các truy vấn mảng, câu trả lời sẽ là tổng các số trong mảng nums [j] trong đó pi <=j
Vì vậy, nếu đầu vào giống như nums =[2, 3, 4, 5, 6, 7, 8, 9, 10], các truy vấn =[(2, 5), (7, 3), (6, 4)] , thì đầu ra sẽ là [13, 9, 8].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
A:=nums
Q:=truy vấn
n:=độ dài của nums
M:=10 ^ 9 + 7
m:=giá trị nguyên của (n ^ 0,5) + 2
P:=một danh sách mới chứa danh sách A m lần
đối với tôi trong phạm vi từ 1 đến m, hãy làm
đối với j trong phạm vi n-1 đến -1, giảm 1, thực hiện
nếu tôi + j
P [i, j]:=(P [i, j] + P [i, i + j]) mô đun M
với mỗi giá trị b, k trong Q, thực hiện
nếu k
trả về [giá trị từ chỉ mục P [k, b]]
nếu không thì
return [sum (A [b to k]) modulo M]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)])) Đầu vào
[2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]
Đầu ra
[13, 9, 8]
