Funcia
Lv.1arraycombinatoricsmath

모든 연속 구간의 합의 합

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

음이 아닌 정수 배열 nums가 주어집니다. 길이가 1 이상인 모든 연속 구간 nums[l..r](0 ≤ l ≤ r < n)에 대해 구간의 합을 구하고, 그 합들을 전부 더한 값을 반환하세요.

답이 매우 커질 수 있으므로 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지를 반환합니다.

입출력 예

numsresult
[1, 2, 3]20
[5]5
[1000000000, 1000000000]999999979

입출력 예 설명

예 1 — 연속 구간은 [1], [2], [3], [1, 2], [2, 3], [1, 2, 3] 여섯 개이고, 합은 각각 1, 2, 3, 3, 5, 6입니다. 모두 더하면 20입니다.

예 2 — 구간은 [5] 하나뿐입니다.

예 3 — 구간 합은 10910^9, 10910^9, 2×1092 \times 10^9이고 총합 4×1094 \times 10^9을 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지는 999999979입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → int

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • 0≤0 \le nums[i] ≤109\le 10^9
  • 답은 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지입니다.

기대 복잡도

시간
O(N)
공간
O(1)

입출력 예

nums기대 출력
[1,2,3]20
[5]5
[1000000000,1000000000]999999979

힌트

힌트

구간을 하나씩 만드는 대신 원소 하나가 몇 개의 구간에 들어가는지 세어 보세요.

nums[i]를 포함하는 구간은 시작점 l을 0..i 중에서(i + 1가지), 끝점 r을 i..n-1 중에서(n - i가지) 고르는 경우이므로 모두 (i+1)(n−i)(i + 1)(n - i)개입니다. 따라서

답=∑inums[i]×(i+1)×(n−i)\text{답} = \sum_i \text{nums}[i] \times (i + 1) \times (n - i)

곱이 64비트 정수를 넘지 않도록 곱할 때마다 나머지를 취하세요. (i+1)(n−i)(i+1)(n-i)는 최대 약 101010^{10}이므로 먼저 나머지를 취한 다음 nums[i]와 곱해야 합니다.

복잡도 목표

시작점마다 끝점을 늘려 가며 합을 누적하는 방법도 O(N2)O(N^2)이라 시간 초과입니다. 원소별 기여도를 더하면 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251022 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.