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

solving linear recurrences
Автор akash2504, 12 лет назад, По-английски

how to solve linear recurrences of the type... f(n) = (n-1) * f(n-1) + (2*n-1) * f(n-2) with matrix exponentiation?

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

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

This type of equations can't be solved with matrix exponentiation.

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

If you consider a sequence f(0), f(1), f(2), .... You may get pair <f(i), f(i + 1)> from <f(i — 1), f(i)> by multiplying on matrix:

M(n) = { {0, 2n-1}, {1, n-1} }

Every multiplication depends on n. So you don't have a fixed matrix to power it. And it may appear impossible to get exact f(n).

But if you calculate modulo MOD. You will get repetition of matrix after MOD multiplications. So you may calculate product M(0) * M(1) * ... * M(MOD-1) = P. And then calculate final matrix as P^(n / MOD) * M(0) * M(1) ... M(n % MOD). The complexity will be O(MOD + log(n)).

If you use chinese theorem, you can calculate modulo several small numbers: MOD1, MOD2, ... MODk (where MODk is the maximal one). Then total Complexity will be O(log(n) + MODk + k^2).

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

    You will get repetition of matrix after M multiplications

    It seems that it must be MOD instead of M.

    Why? It looks like Fermat's little theorem for matrix. Is it correct?

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

      Fixed.

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

      I don't see any connection with the Fermat little theorem. Repetition will be, because if you calculate modulo MOD, then you may take reminder for any member of multiplication. It is easy to prove that: M(n) % MOD = M(n + MOD) % MOD. So when we calculate by modulo repetition will appear.

      → Ответить