### om1429888's blog

By om1429888, history, 6 weeks ago,

Hi guys. We all know that matrix exponentiation can be used to find Nth term of a recurrent relation in logN time, this is generally used to find Nth fibonacci in logN time where N can be as large as 1e18(obviously it is modulo something), now fibonacci is represented as f(n-1)+f(n-2),but what is relation isnt linear, it can be for example, f(n-1)+f(n-2)+f(n-1)*f(fn-2). i tried and could'nt find a solution, so any suggestions>

• +16

 » 6 weeks ago, # |   +23 NewbiesHow to solve problems with matrix exponentiation? Me in a roundLooks like a matrix exponentiation problem,I will skip that.
•  » » 6 weeks ago, # ^ |   +3 lmao, thanks for the advice.
•  » » 6 weeks ago, # ^ |   0 Me solving those problemsHaha Berlekamp-Massey go BRRRRRRRRRRRRRR realitynever really met one of those problems in a contest though...
 » 6 weeks ago, # |   +5 Mathematical savvy should help you. For example Solving Non Linear Recurrence Relation. In our case we can rewrite the recurrence as $f[n] + 1 = f[n-1] * f[n-2] + f[n-1] + f[n-2] + 1 = (f[n-1] + 1) * (f[n-2] + 1)$Or if we denote $g_n = f[n] + 1$we have $g_n = g_{n-1} g_{n-2}$If our initial conditions are $f[0] = b, f[1] = a$(and nonzero) then $f[n] = (a + 1)^{F_n} (b + 1)^{F_{n-1}} - 1$where $F_n$ is $n$-th Fibonacci number ($F_2 = F_1 = 1$). The case with zero $a$ or $b$ is simple.
•  » » 6 weeks ago, # ^ |   0 thanks alot.can u help me with another doubt please?
•  » » » 6 weeks ago, # ^ |   0 I'll try.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 do u have any idea about this? https://codeforces.com/blog/entry/106054#comments
 » 6 weeks ago, # | ← Rev. 2 →   0 maybe this video can give u an intution