Subsequence-Numbers Divisible by 7 solution codechef

Subsequence-Numbers Divisible by 7 solution codechef

Kulyash has given you an array AA of size NN.

He defines the subsequence-number of a non-empty subsequence SS of array AA as the number formed by the concatenation of all the elements of the subsequence SS.

Find the count of non-empty subsequences of AA having their subsequence-numbers divisible by 77. Since the answer can be huge, output it modulo 109+7109+7.

For example: Consider A=[1,2,3,4,5,6,7,8,9,10]A=[1,2,3,4,5,6,7,8,9,10]. A subsequence SS of AA is [2,5,7,10][2,5,7,10]. The subsequence-number of this subsequence is 2571025710.

Input Format

• The first line will contain TT, the number of test cases. Then the test cases follow.
• The first line of each test case contains one integer NN, the size of the array.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN — the elements of the array AA.

Output Format

For each test case, output in a single line the number of subsequences with subsequence-number divisible by 77 modulo 10000000071000000007.

Subsequence-Numbers Divisible by 7 solution codechef

• 1≤T≤10001≤T≤1000
• 1≤N≤3⋅1051≤N≤3⋅105
• 1≤Ai≤3⋅1051≤Ai≤3⋅105
• Sum of NN over all test cases does not exceed 3⋅1053⋅105

Sample Input 1 

3
2
1 2
4
1 2 3 4
2
7 7

Sample Output 1 

0
1
3

Subsequence-Numbers Divisible by 7 solution codechef

Test case 11: Only 33 subsequences are possible for the given array. These are [1][1], [1,2][1,2], and [2][2]. The subsequence-numbers are 11, 1212, and 22 respectively. None of the subsequence-numbers are divisible by 77, so the answer is 00.

Test case 22: [1,4][1,4] is the only subsequence having its subsequence-number 1414 which is divisible by 77. So, the answer is 11.

Test case 33: All the non-empty subsequences [7][7], [7][7], and [7,7][7,7] have their subsequence-numbers 7,7,7,7, and 7777 divisible by 77. So, the answer is 33.

SOLUTION

“Click here“