MPOW - Power of matrix
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.)
Input
First line of input is T (number of test-cases) First line of each test-case contains two integer M and N, where M is size of square matrix that we have to exponent and N is the power to which we have to exponent it. The next M lines describe the input matrix. Each line contains exactly M elements corresponding to each array
Output
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 (109+7).
Simply, you have to print the resultant square matrix.
Example
Input: 2 2 3 1 0 1 1 3 3 1 0 4 1 2 2 0 4 4 Output: 1 0 3 1 17 112 116 15 88 100 28 144 160
Constraints
1 ≤ T ≤ 10
1 ≤ M ≤ 50
1 ≤ N ≤ 100000
0 ≤ each element of input matrix ≤ 109
hide comments
tush_chen:
2020-11-13 07:20:33
If anyone is getting TLE even after using the modulo operator with prudence, make sure you are passing your vectors by reference and not value, took me a while to figure that out :( |
|
iamblank_99:
2020-10-06 15:45:11
if anyone is here after watching the CodeNcode video do this in multiplication operator :-
|
|
md__talha__007:
2020-10-02 08:27:01
Can any one help me
|
|
aanchal_2894:
2020-09-12 01:06:49
i am getting tle in python . i used matrix exponentiation method. Last edit: 2020-09-12 01:07:38 |
|
alamgir58:
2020-09-04 08:29:06
0.07sec && 4.7MB |
|
mdyamin:
2020-07-28 13:30:49
If you can't figure out why you are getting wa then use long long and use modular arithmetic wisely. |
|
kishlay1105:
2020-07-27 08:49:39
->If you are not able to build logic , see code Ncode video on matrix exponentiation.
|
|
fuadul_hasan:
2020-07-16 09:50:28
after 4 days of thinking and getting lot of wa finally i come with a solution and it's accepted. codeNcode help a lot for this problem. but it's easy to think Matrix struct for this problem. its make sense to me. Last edit: 2020-07-16 09:51:12 |
|
amb_2020:
2020-07-09 21:44:59
I have followed all the suggestions from the comments but still I am getting WA
|
|
coding_sourabh:
2020-07-08 14:02:18
remember to use mod correctly gave me many WA. |
Added by: | ivar.raknahs |
Date: | 2014-12-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own |