I have a problem and do not know how to solve it. that is:
Give a matrix A size of nxn. The task is computing sum of A + A^2 + ... + A^k.
INPUT:
— First line: n, k
— Following n lines, each give n integer
OUTPUT:
— Result matrix with element is remain of module 10
Constraint:
n <= 20
Aij, k <= 10^9
Example:
INPUT:
2 3
0 1
1 1
OUTPUT:
2 4
4 6
This just my homework and i do not have any more test.
Can someone give me some ideal to solve this?
Thanks in advance.
(sorry if my English bad)
F(k) = A + A^2 + ... + A^k
F(k * 2) = F(k) + F(k) * A^k
F(k * 2 + 1) = F(k * 2) + A^(k * 2 + 1)
also you can use this idea
thank you. i got it. :D
Two matrixes multiplation complexity is O(n^3) , then :
Did you see that , divide from middle is works , it is just like fast multiplation in O(log k) so overall complexity is O(n^3logk)
here is pseudo code :
EDIT: well i didnt see goo.gl_SsAhv 's comment because it was 1 minute ago from me:(
thank you. i got it. :D