You will be given a square matrix M and a positive integer power N. You will have to compute M raised to the power N. (that is, M multiplied with itself N times.)
The problem wants you to multiply matrix to itself n times which is a difficult job if you perform it by normal iteration method so you are required to think an approach such that it provides correct solution with minimum time ,think some logic similar to binary exponentiation technique that we use to calculate power of number n times as power(x, n) such that we use logarithmic time.
The first line of input is T (number of test-cases) First line of each test case contains two integer M, N where M is the size of the square matrix that we have to exponent and N is the power to which we have to, exponent.
Next M lines describe the input matrix. Each line contains exactly M elements corresponding to each array
Output M line corresponding to each row of resultant matrix Each line must have M integers where jth element of ith line is jth element of resultant matrix taken modulo with 1000000007 (10^9+7).
Input: T=1 M=2,N=3 1 0 1 1 Output: 1 0 3 1 Input: T=1 M=3,N=3 1 0 4 1 2 2 0 4 4 Output: 17 112 116 15 88 100 28 144 160
(a) Brute Force Approach:
In this approach, we will multiply the given matrix M, N number of times. Each time the multiplication will cost O(M^3) time in the worst case and we multiplied it N numbers of times so the overall time complexity will be O(N*M^3) which will be huge.
Since the given operation is on the matrix so we cant multiply it similar to normal mathematical variables, we will multiply it with its Identity matrix of the same size as of given matrix M, we will store the result in the final result in the given matrix after performing all multiplication.
Here we are using function multiply which will take two matrices and multiply them and store the result in the first matrix, solve function which will take matrix as given in the question and all the operation from creating identity matrix and calling multiply function and then storing the final result in the given matrix. The print function will print the final matrix that we get after all operations.
Time Complexity for the above operation in the worst case is: O((M^3)*N)
Space Complexity for above operation in the worst case is: O(M*M)
(b) Matrix Exponentiation Method:
In this approach all operation is the same except the multiplication operation, instead of traversing from 1 to N, we will multiply matrix using binary exponentiation logic. That is each when our power (N) is odd we multiply Identity matrix with the given matrix that is (I*A) and decrease power variable N--, and in even condition, we will multiply a matrix with itself, that is (A*A) and divide power by 2 i.e (N/2).
So we can multiply the given matrix N number of times in log(N) time.
So overall we saved a lot of time.
Time Complexity for the above approach in worst case: O((M^3)*(log(N))
Space Complexity for the above approach in worst case: O(M*M)
C++ Implementation (Brute Force Approach):
C++ Implementation (Optimized Method - Matrix Exponentiation)
Output:need an explanation for this answer? contact us directly to get an explanation for this answer