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

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

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
14 лет назад, скрыть # |
← 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).

→ Ответить