SEQAGAIN Sequence

how to solve this Problem.

since n can be of the order 10^18, can it really be solved using just memoization(i don’t think so) ? can this problem be solved using matrix exponentiation, but the recurrence is not linear. Help.

[EDIT]:
I came up with THIS CODE, can anyone point out why it is giving wrong answer ?

It can be solved using matrix exponentiation if you take log. Then define new sequence which is:

G(n)=log(F(n)).

Then the question is reduced to standard recurrence solving where the matrix first row is :[k,k] instead of [1,1].

2 Likes

wow!! beautiful solution…
doubt.
the column vector then becomes [log(f(n-1)), log(f(n-2))]. So, don’t you think taking log will include float number in the calculation and then finally when we will take anti log answer might be off some digits ?

@ashwanigautam

You dont actually need to take log on values. It was for explanation purpose. Using the property:

a^(log b(base a) ) = b, you can avoid log and double and smoothly work with long integers.

hey!! i understood what you said. here is my solution http://ideone.com/m19TN6
Its not very long :). but it is giving wrong answer, i don’t know why. can you tell me whats wrong with it ?

in matrix multiplication, replace mod by (mod-1) and get AC!

and the reason is ? stil not getting AC http://ideone.com/sPPc4a, care to try ?