### 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> Comments (8)
 » NewbiesHow to solve problems with matrix exponentiation? Me in a roundLooks like a matrix exponentiation problem,I will skip that.
•  » » lmao, thanks for the advice.
•  » » Me solving those problemsHaha Berlekamp-Massey go BRRRRRRRRRRRRRR realitynever really met one of those problems in a contest though...
 » 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 = b, f = 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.
•  » » thanks alot.can u help me with another doubt please?
•  » » » I'll try.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   do u have any idea about this? https://codeforces.com/blog/entry/106054#comments
 » 6 weeks ago, # | ← Rev. 2 →   maybe this video can give u an intution