Consecutive Product Sum

Practice

4 (2 votes)

Algorithms

Math

Combinatorics

Basics of combinatorics

Problem

57% Success 316 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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

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\)

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Results

Custom Input

Run your code to see the output

Submissions

Please login to view your submissions