Funcia
Lv.1arraycombinatoricsmath

Sum of All Subarray Sums

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given a non-negative integer array nums, add up the sums of all non-empty contiguous subarrays nums[l..r] and return the total modulo 1,000,000,0071{,}000{,}000{,}007.

Examples

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

Example 1 — the subarray sums are 1, 2, 3, 3, 5, 6, totalling 20.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[]) → int

Constraints

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • 0≤0 \le nums[i] ≤109\le 10^9
  • Return the answer modulo 1,000,000,0071{,}000{,}000{,}007.

Expected complexity

Time
O(N)
Space
O(1)

Examples

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

Hint

Hint

Count how many subarrays contain nums[i]: i + 1 choices of start and n - i choices of end, so the answer is ∑inums[i](i+1)(n−i)\sum_i \text{nums}[i] (i + 1)(n - i). Reduce (i+1)(n−i)(i+1)(n-i) (up to about 101010^{10}) modulo 109+710^9+7 before multiplying by nums[i] so 64-bit arithmetic does not overflow. Extending a running sum from every start is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251022 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.