You are not logged in. Please login at www.codechef.com to post your questions!

×

CPH003C - Editorial

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.

This question is marked "community wiki".

asked 25 Jan, 00:06

sonu_628's gravatar image

4★sonu_628
3288
accept rate: 8%

edited 01 Feb, 01:23

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,441
×3,202
×251
×132
×10

question asked: 25 Jan, 00:06

question was seen: 274 times

last updated: 01 Feb, 01:23