CPH003C - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Deepansh Parmani
Tester: Karan Malhotra, Dushyant Singh
Editorialist: Deepansh Parmani

DIFFICULTY:

EASY,

PREREQUISITES:

Loops,Fibonacci

PROBLEM:

Defining F(i) as F(i) = F(i-1) + 2*F(i-2) , 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

F(1) = 1.a + 0.b
F(2) = 0.a + 1.b
F(3) = 2.a + 1.b
F(4) = 2.a + 3.b
F(5) = 6.a + 5.b
F(6) = 10.a + 11.b
.
.
.

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[i-1]) + 2*(times a in F[i-2])

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[i-1] + 2*A[i-2] % mod

and

B[i] = B[i-1] + 2*B[i-2] % 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.
Tester’s solution(Karan Malhotra) can be found here.