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>

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

Or if we denote

we have

If our initial conditions are

(and nonzero) then

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.

do u have any idea about this? https://codeforces.com/blog/entry/106054#comments

maybe this video can give u an intution