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

Matrix exponentiation
Автор patience, история, 9 лет назад, По-английски

Given a Matrix n*n size Let the matrix is A .. Now i have to find out.. A+A^1+A^2+A^3+.......+A^k(k=10^9).. i only can find out the A^k using matrix exponentiation... how can i find the solution of the above equation..

EXAMPLE:
n=3,k= 2
  1 4 6
A=6 5 2
  1 2 3
output:
208
484
722

problem link:http://lightoj.com/volume_showproblem.php?problem=1142

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

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

This was discussed many times already: A + A2 + A3 + ... + A2n = (I + AN)(A + A2 + A3 + ... + AN)

When n is odd you just find An and get again to the case when n is even.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    You need to calc A^n each time. You may use formulas that doesn't require it

    (I + A)(I + A2 + (A2)2 + (A2)3 + ... + (A2)n) for odd.
    I + A(I + A + A2 + A3 + ... + An - 1) for even

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

Here is another way to calculate that power-sum. Build a new 2n × 2n matrix . Taking B to the kth power gives . This is easy to prove by induction.

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

To solve the problem, I use classical matrix exponentiation to the following recurrences:

f(0)=A, f(n)=A*f(n-1)

g(0)=O, g(n)=g(n-1)+f(n-1)

This is my code, maybe this help you.

→ Ответить