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].
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 ?
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!
link not working!
try this http://ideone.com/sQfhNa , can you please explain the reason meanwhile.
I can see that you mean, we have to take the mod to be equal to its euler totient number during matrix exponentiation, but i don’t see the WHY behind it. :\
You are right. This is because you will raise them to power of integers, and its direct result of Fermat’s Theorem. Also, use long for n.
i know about Fermat theorem it says a^phi(n) is = 1 mod(n) so if we are given, a^k mod(n), we can reduce it to a^(k mod( phi(n) ) ) mod(n). right ? we still have to take the number mudulo n(and not phi(n)) after exponentiation right ?
so first. it reduces the exponent which seems to be an optimization as we are already doing binary exponentiation.
second, does this hold for matrix as well, as we know the equation holds only if a belongs to multiplicative modulo group of n, that is, if they are co-prime, so how can we say a matrix is co-prime to a number ? links are welcome too. 
i dont know whether they hold for matrices!