PROBLEM LINK:Author: Deepansh Parmani DIFFICULTY:EASY, PREREQUISITES:Loops,Fibonacci PROBLEM:Defining F(i) as F(i) = F(i1) + 2*F(i2) , given F(1) = a and F(2) = b find out F(i)%1000000007 t times QUICK EXPLANATION:the numbers of occurrences of a and b in F(i) is itself a fibonacci series EXPLANATION:If we observe the patter we will find that number of times a and b are present in F(i) is itself a a fibonacci sequence
1,0,2,2,6,10... and 0,1,1,3,5,11 are itself following the pattern i.e any number is sum of previous and twice the previous's previous let hence number of times a is added is in F[i] will be  (times a in F[i1]) + 2*(times a in F[i2]) $$let \space A[i] \space be \space ith \space integer \space in \space pattern \space 1,0,2,2,6,10... $$ $$let \space B[i] \space be \space ith \space integer \space in \space pattern \space 0,1,1,3,5,11... $$ then \begin{equation} A[1] = 1 \space and \space A[2] = 0 \end{equation} and \begin{equation} B[1] = 0 \space and \space B[2] = 1 \end{equation} and $$ A[i] = A[i1] + 2*A[i2] % mod $$ and $$ B[i] = B[i1] + 2*B[i2] % mod $$ then we can precompute A[i] and B[i] upto to maximum value of n i.e is 10^5 then our ans is simply is (A[i].a + B[i].b) Also we need to take mod with 1e9+7 at each step ALTERNATIVE SOLUTION:This question can be solved using matrix exponentiation in O(log(n)). Using this method we can calculate F(i) where i upto 10^18 .More about Matrix Exponentiation . This is shown in testers solution AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 25 Jan '18, 00:06
