Sum of Interval Products

Frequency: Reported

Given an array of N positive integers a[0], ..., a[N - 1], return the sum of the products of all contiguous intervals, modulo (10^9 + 7):

text

\sum_{i=0}^{N-1}\sum_{j=i}^{N-1}\prod_{k=i}^{j} a_k \pmod{10^9+7}.

Function

python

def intervalProducts(a):

Constraints

text

1 <= N <= 10^5
1 <= a[i] <= 10^9

Submitted implementation

python

def intervalProducts(a):
    MOD = 10**9 + 7
    n = len(a)
    res = 0
    prod = [1] * (n + 1)

    for i in range(n):
        prod[i + 1] = (prod[i] * a[i]) % MOD

    for i in range(n):
        curr = 1
        for j in range(i, n):
            curr = (curr * a[i]) % MOD
            res = (res + curr) % MOD

    return res

The code is transcribed as submitted. It multiplies by a[i] inside the inner loop rather than a[j], and the computed prod array is never used.