Consecutive Product Sum

★★★★★

2 votes

Algorithms, Math, Combinatorics, Basics of Combinatorics

Details

Problem

The score of an Array $S$ of length $N$ is defined as $\sum_{i=0}^{N-2} S_i \cdot S_{i+1}$ , i.e. sum of product of every consecutive pair of elements.

Given an Array $arr$ of length $N$ find the sum of scores of every subsequence of $arr$ of length atleast $2$ , return the sum modulo $10^9 + 7$ .

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input Format:

First line contains an integer $T$ denoting the number of test cases.
First line of each testcase contains an integer $N$ denoting length of $arr$ .
Next line contains $N$ space-seperated integer, denoting the elements of $arr$ .

Output Format:

For each testcase, print the sum of scores of every subsequence of $arr$ having length atleast $2$ , modulo $10^9 + 7$ .

Constraints:

$1 \le T \le 10$
$2 \le N \le 5 \times 10^5$
$0 \le arr[i] \le 10^4$

Sample Input

5
4
1 1 2 3
7
1 1 1 1 1 1 1
4
1 0 1 0
10
1 2 3 4 5 6 7 8 9 10
10
9990 9991 9992 9993 9994 9995 9996 9997 9998 9999

Sample Output

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

First Sample Case

First Subsequence is $[1, 1]$

Score is $1 \times 1$ = $1$

Second Subsequence is $[1, 2]$ and appears $2$ times

Score is $1 \times 2$ = $2$ added $2$ times

Third Subsequence is $[1, 3]$ and appears $2$ times

Score is $1 \times 3$ = $3$ added $2$ times

Fourth Subsequence is $[2, 3]$

Score is $2 \times 3$ = $6$

Fifth Subsequence is $[1, 1, 2]$

Score is $1 \times 1 + 1 \times 2$ = $3$

Sixth Subsequence is $[1, 1, 3]$

Score is $1 \times 1 + 1 \times 3$ = $4$

Seventh Subsequence is $[1, 2, 3]$ and appears $2$ times

Score is $1 \times 2 + 2 \times 3$ = $8$ added $2$ times

Eighth Subsequence is $[1, 1, 2, 3]$

Score is $1 \times 1 + 1 \times 2 + 2 \times 3$ = $9$

Sum of score for every subsequence = $49$

Second Sample Case

First Subsequence is $[1, 1]$ and appears $21$ times

Score is $1 \times 1$ = $1$ added $21$ times

Second Subsequence is $[1, 1, 1]$ and appears $35$ times

Score is $1 \times 1 + 1 \times 1$ = $2$ added $35$ times

Third Subsequence is $[1, 1, 1, 1]$ and appears $35$ times

Score is $1 \times 1 + 1 \times 1 + 1 \times 1$ = $3$ added $35$ times

Fourth Subsequence is $[1, 1, 1, 1, 1]$ and appears $21$ times

Score is $1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1$ = $4$ added $21$ times

Fifth Subsequence is $[1, 1, 1, 1, 1, 1]$ and appears $7$ times

Score is $1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1$ = $5$ added $7$ times

Sixth Subsequence is $[1, 1, 1, 1, 1, 1, 1]$

Score is $1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1$ = $6$

Sum of score for every subsequence = $321$

Third Sample Case

First Subsequence is $[1, 1]$

Score is $1 \times 1$ = $1$

Second Subsequence is $[1, 1, 0]$

Score is $1 \times 1 + 1 \times 0$ = $1$

Every other subsequence has score $0$

Sum of score for every subsequence = $2$

Contributers:

Abhishek Choudhary

Madhumeeta Bauk