Блог пользователя ivplay

my idea LightOj 1142(matrix exponentiation)
Автор ivplay, 10 лет назад, По-английски

  • This post is for those beginners who want to learn and practice matrix exponentiation. I am just here to share my idea on a very basic problem form lightoj(1142).

  • Task is simple A + A^2 + A^3 + ... + A^k =? where A is a n*n matrix.

  • First time I thought ans will progress as geometric sum = (A*((A^k)-1))/A-1. or we can say... (A^(k+1) — A)/(A-1) where one is an Identity matrix. I was stuck in the matrix division portion for a long time. I don't know whether my geometric sum idea is right or wrong but i have another idea that can avoid that division.
  • say A + A^2 + A^3 + ... + A^k = f(k)
  • if(k is even,say k= 2x) we can write
  • f(k=2x) = [A + A^2 + A^3 + ... + A^x ] + [A^(x+1) + A^(x+2) + .... + A^(x+x)]
  • = [A + A^2 + A^3 + ... + A^x ] + [A^x(A + A^2 + A^3 + ... + A^x)]
  • = [A + A^2 + A^3 + ... + A^x ] * (A^x + 1)
  • = f(k/2) * (A^(k/2) + 1)
  • else if K is odd we can write
  • f(K)= [A + A^2 + A^3 + ... A^(k-1)] + A^k = f(k-1)+A^k
  • very good problem for beginners. You can try if you have just started to learn matrix exponentiation.
  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Nice explanation. I think there is a typo in the else part, it should be odd rather than even.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

nice.

→ Ответить
»
10 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

nice explanation.
complexity seems to be (where is the size of matrix ).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't think so. Nobody can mutiply matrices in O(n2).

    We can maintain needed powers of A, so complexity is

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What about the correctness of this way, sum = (A^(k+1) — A)/(A-1) ? Is this method right? If it is right, we calculate in O((logk) * n^3).

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't we write the recurrence as F(k)=A(1+A(A+A^2+...+A^k-1))=A(1+A*F(k-1))=(A^2)F(k-1)+A

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great explanation thanks

→ Ответить