×

# CPH003C - Editorial

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

EASY,

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 $$A[1] = 1 \space and \space A[2] = 0$$

and $$B[1] = 0 \space and \space B[2] = 1$$

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.

This question is marked "community wiki".

3★sonu_628
3468
accept rate: 8%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,526
×3,711
×284
×137
×10

question asked: 25 Jan '18, 00:06

question was seen: 359 times

last updated: 01 Feb '18, 01:23