[Solution] Sum of Product 1 solution codechef

Sum of Product 1 solution codechef – For an array A of length N, let F(A) denote the sum of the product of all the subarrays of A. Formally,

Table of Contents

[Solution] Sum of Product 1 solution codechef

F(A) = \sum_{L=1}^N \sum_{R=L}^N \left (\prod_{i=L}^R A_i\right )

For example, let A = [1, 0, 1], then there are 6 possible subarrays:

  • Subarray [1, 1] has product = 1
  • Subarray [1, 2] has product = 0
  • Subarray [1, 3] has product = 0
  • Subarray [2, 2] has product = 0
  • Subarray [2, 3] has product = 0
  • Subarray [3, 3] has product = 1

So F(A) = 1+1 = 2.

Given a binary array A, determine the value of F(A).

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integer N denoting the length of the array.
    • The second line contains N space-separated integers denoting the array A.

Output Format

For each test case, output on a new line the value of F(A).

[Solution] Sum of Product 1 solution codechef

  • 1 \leq T \leq 1000
  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq 1
  • The sum of N over all test cases won’t exceed 2 \cdot 10^5.

Sample 1:

Input

Output

4
3
1 0 1
1
0
2
1 1
4
1 1 0 1
2
0
3
4

[Solution] Sum of Product 1 solution codechef Explanation:

Test case 1: Explained in the statement.

Test case 2: There is only 1 subarray and it has product = 0.

Test case 3: All the 3 subarrays have product = 1.

For Solution

Click Here

Leave a Comment