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.

Through this contest, selected students get access to a free 6 month LinkedIn Premium subscription which helps students:

  • Discover & apply to 20M+ jobs/internships on LinkedIn
  • Reach out to hiring managers/recruiters/mentors directly
  • Find career paths that people similar to them have taken
  • Learn from over 17K expert-led LinkedIn Learning courses (technical & soft-skills) with certificates

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

  • 1T10001≤T≤1000
  • 1N31051≤N≤3⋅105
  • 1Ai31051≤Ai≤3⋅105
  • Sum of NN over all test cases does not exceed 31053⋅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 111212, 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

Leave a Comment

Your email address will not be published.