GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Friday 20 May 2022

Subsequence-Numbers Divisible by 7 CodeChef Solution | CodeChef Problem Solution 2022

Kulyash has given you an array A of size N.

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

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

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

Solution Click Below:-  CLICK HERE

Input Format

  • The first line will contain T, the number of test cases. Then the test cases follow.
  • The first line of each test case contains one integer N, the size of the array.

  • The second line of each test case contains N space-separated integers A1,A2,,AN — the elements of the array A.

Output Format

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

Constraints

  • 1T1000
  • 1N3105
  • 1Ai3105
  • Sum of N over all test cases does not exceed 3105

No comments:

Post a Comment