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].
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.
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 ?
hey!! i understood what you said. here is my solution m19TN6 - Online C++0x Compiler & Debugging Tool - Ideone.com
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 sPPc4a - Online C++0x Compiler & Debugging Tool - Ideone.com, care to try ?
link not working!
try this sQfhNa - Online C++0x Compiler & Debugging Tool - Ideone.com , 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!