dungqt3's blog

matrix problem
By dungqt3, 11 years ago, In English

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)

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Two matrixes multiplation complexity is O(n^3) , then :

A + A^2 + A^3 + A^4 + A^5 + A^6
(A^3) * (A + A^2 + A^3) + A + A^2 + A^3

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 : 

f(k) =  if "k is even"  f(k / 2) +  f(k / 2) * (A ^ (k/2)) 
        else f(k / 2) + f(k / 2) * (A ^ (k/2)) + (A ^ k)

EDIT: well i didnt see goo.gl_SsAhv 's comment because it was 1 minute ago from me:(

→ Reply