Play with a matrix
Practice
1 (3 votes)
Arrays
Data structures
Multi Dimensional
Medium
Mathematics
Problem
69% Success 143 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given a 1-D array of size \(N\). You are required to create a square matrix of size \( \sqrt{N} \times \sqrt{N} \). The creation of a matrix is done by selecting first \( \sqrt{N} \) elements from the array for the first row of the matrix, then next \( \sqrt{N} \) elements for the second row and this goes up to for \( {(\sqrt{N})}^{th} \) row. There is also a possibility that some elements of the array may not be used for creating a square matrix. You are also given an integer \(K\), you have to circularly right shift the \( 1-D \) array by one for \(K\) times and for every shifting, a new \( 1-D \) array or better say new square matrix is formed. After shifting for \(K\) times, you come up with total \( K + 1 \) square matrices.

For example, if the given array is \( (2,3,4,5,6) \) and the value of \(K\) is 2. The size of the square matrix is \( \sqrt{5} \) i.e. \( 2 * 2 \).

An initial square matrix is defined as \( m0[0][0]=2, m0[0][1]=3, m0[1][0]=4, m0[1][1]=5\).

For \( K = 2 \), we need to circularly right shift array by one twice. Therefore, after the first circular right shift, the array becomes \( (6,2,3,4,5) \) and the new square matrix \( m1 \) is defined as \( m1[0][0]=6, m1[0][1]=2, m1[1][0]=3, m1[1][1]=4\).

Similarly, after the second circular right shift, the array becomes \( (5,6,2,3,4) \) and the square matrix \( m2 \) is defined as \( m2[0][0]=5, m2[0][1]=6, m2[1][0]=2, m2[1][1]=3 \).

Now, you are required to determine the multiplication of these \( (K + 1) \) matrices and print the sum of resultant elements of the square matrix.

Since answer can be large, print it modulo \( 10^9+7 \).

Input format

  • First line: Two integers \(K\) and \(N\) denoting the number of circular right shifts and the size of the 1-D array respectively
  • Next line: \(N\) space-separated integers denoting elements of \( 1-D \) array

Output format

Print an integer that denotes the sum of all the elements of the resultant matrix. Since answer may be large, print it modulo \( 10^9+7 \).

Constraints

\( 1 \leq N \leq 1000 \)

\( 0 \leq A[i] \leq 10^9 \)

\( 1 \leq K \leq 10^{15} \)

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

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
1 votes
Tags:
Grammar-VerifiedReadyRecruitApprovedReadyGrammar-VerifiedRecruitApprovedReadyCombinatoricsHardBasics of CombinatoricsBasic ProgrammingCombinatorics basicsMathematicsMath
Points:20
19 votes
Tags:
Advanced Data StructuresBit ManipulationData StructuresEasySegment Trees
Points:30
10 votes
Tags:
AlgorithmsDepth First SearchGraphsMedium