PLUSMUL - Editorial

editorial
1

PROBLEM

You are given an array A consisting of N integers. For each number A_i, i from 2 to N, you can decide to put either a +, plus or a *, multiplication sign before it. After putting the N-1 signs, you evaluate the expression. You have to find the sum of the values of the all 2^{N-1} such expressions. Output your answer modulo 10^9 + 7.

Note that multiplication sign has higher priority than plus sign. For example, the value of the expression 2 + 2 * 2 will be 2 + 4 = 6.

SOLUTION

The problem can be solved using dynamic programming. Let dp[i] denote the sum of values of expressions made using first i elements of the array. Our answer will be dp[n].

We can find the recurrence relation for dp[i] as follows. Let j be the largest index \leq i, such that we decide to put a plus sign before A_j. That means that all the signs between the numbers from A_j to A_i are all multiplication signs. Let p[j,i] denote the product of numbers A_k where j \leq k \leq i. Note that dp[j - 1] denotes the sum of values of the 2^{j-2} expressions of first j-1 values of array A. We add value p[j.i] in each of these expressions. So, overall contribution due to a fixed j will be dp[j-1] + p[j.i] \cdot 2^{j-2}.

Hence, the recurrence relation for dp[i] will be as follows.

dp[0] = 0
dp[1] = A[1]

For i > 1,

dp[i] = \sum_{j = 1}^{i} dp[j-1] + p[j.i] \cdot 2^{j-2}

Calculating dp using this expression will take quadratic time in terms of N, the size of the array A. We want to compute it faster.

Let prod[i] denote the product of first i elements of array A, modulo 10^9 + 7. We can write p[j.i] as \frac{prod[i]}{prod[j-1]}, i.e. prod[i] * prod[j - 1]^{-1} modulo 10^9 + 7. So, the recurrence relation now becomes.

dp[i] = \sum_{j = 1}^{i} (\, dp[j-1] + prod[i] * prod[j - 1]^{-1} \cdot 2^{j-2}) \,
dp[i] = \sum_{j = 1}^{i} dp[j-1] \quad + \quad prod[i] \sum_{j = 1}^{i} prod[j - 1]^{-1} \cdot 2^{j-2}

Suppose you maintain a prefix sum dp array sdp[i] which will store the sum of dp[0] + dp[1] + dp[2] + \dots + dp[i-1], and a prefix sum array extra[i] which stores sum of prod[j - 1]^{-1} \cdot 2^{j-2} for j from 1 to i. After this, you can write your updated recurrence relation as follows.

dp[i] = sdp[i] + prod[i] * extra[i]

You can maintain arrays dp, sdp, prod, extra in a single iteration over the array. Overall time complexity of this will be \mathcal{O}(n \cdot \log{10^9 + 7}). The \log{10^9 + 7} is accounted towards finding the inverse of a number modulo 10^9 + 7.