bayram's blog

matrix power
By bayram, 12 years ago, In English

Can anyone explain O(log(n)) solution for this problem with matrix power.
Thanks for your helping!

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

»
12 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it 
s[i] = (a, b, c, d)
=>
s[i + 1].a = s[i].b + s[i].c + s[i].d
s[i + 1].b = s[i].a + s[i].c + s[i].d
s[i + 1].c = s[i].a + s[i].b + s[i].d
s[i + 1].d = s[i].a + s[i].b + s[i].c
=>
s[i + 1]  = s[i] * ( 0 1 1 1 ) = s[i] * M
                   ( 1 0 1 1 )
                   ( 1 1 0 1 )
                   ( 1 1 1 0 )
=>
s[i + k] = s[i] * (M pow k)
=>
s[0].d = 1;
s[n] = s[0] * (M pow n)
ans = s[n].d
→ Reply
»
12 years ago, hide # |
 
Vote: I like it -24 Vote: I do not like it

The fastest matrix multiplication algorithm is Strassen_algorithm then you have to apply Binary Exponentiation .

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Tetrahedron can be represented as a graph with 4 vertices and problem is to count number of ways with fixed length K. There is an explanation of the solution with matrix exponentiation: here

→ Reply