Sum of products of elements of all subarrays of length k

Question

An array of length n is given. Find the sum of products of elements of the sub-array.

Explanation

Array A = [2, 3, 4] of length 3.

Sub-array of length 2 = [2,3], [3,4], [2,4]

Product of elements in [2, 3] = 6

Product of elements in [3, 4] = 12

Product of elements in [2, 4] = 8

Sum for subarray of length 2 = 6+12+8 = 26

Similarly, for length 3, Sum = 24

As, products can be larger for higher lengths of sub-arrays calculate in modulo 1000000007.

What is an efficient way for finding these sums for subarrays of all possible lengths, i.e., 1, 2, 3, ......, n where n is the length of the array.

Answer 1

There is rather simple way:
Construct product of terms (1 + A[i] * x):

P = (1 + A[0] * x) * (1 + A[1] * x) * (1 + A[2] * x)...*(1 + A[n-1] * x)

If we open the brackets, then we'll get polynomial

P = 1 + B[1] * x + B[2] * x^2 + ... + B[n] * x^n

Kth coefficient, B[k], is equal to the sum of products of sets with length K - for example, B[n] = A[0]*A[1]*A[2]*..A[n-1], B[2] = A[0]*A[1] + A[0]*A[2] + ... + A[n-2]*A[n-1] and so on.

So to find sum of products of all possible sets, we have to find value of polynomial P for x = 1, then subtract 1 to remove leading 0th term. If we don't want to take into consideration single-element sets, then subtract B1 = sum of A[i].

Example:

(1+2)(1+3)(1+4) = 60
60 - 1 = 59
59 - (2 + 3 + 4) = 50 = 24 + 26 - as your example shows