양의 정수를 포함하는 크기가 n인 배열 'nums'가 있다고 가정합니다. 정수 쌍(pi, qi)을 포함하는 또 다른 배열 '쿼리'가 있습니다. 배열 쿼리의 모든 쿼리에 대해 대답은 배열 nums[j]에 있는 숫자의 합이 됩니다. 여기서 pi <=j
따라서 입력이 nums =[2, 3, 4, 5, 6, 7, 8, 9, 10]과 같으면 쿼리 =[(2, 5), (7, 3), (6, 4)] , 출력은 [13, 9, 8]이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
A :=숫자
Q :=쿼리
n :=숫자의 길이
남 :=10^9 + 7
m :=(n ^ 0.5) + 2의 정수 값
P :=목록을 포함하는 새 목록 A m 번
범위 1에서 m에 있는 i에 대해 수행
n-1 ~ -1 범위의 j에 대해 1 감소, 수행
i+j
P[i, j] :=(P[i, j]+P[i, i+j]) 모듈로 M
Q의 각 값 b, k에 대해 수행
k
반환 [인덱스 P[k, b]의 값]
그렇지 않으면
return [sum(A[b to k]) 모듈로 M]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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)])) 입력
[2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]
출력
[13, 9, 8]
