SRTX16B - Editorial

PROBLEM LINK:

Practice

Contest

Author: Suraj Kumar

Tester: Priyanshu Jain

DIFFICULTY:

EASY

PREREQUISITES:

Matrix form of Fibonacci numbers, Binary exponentiation.

PROBLEM:

You just need to find the nth Fibonacci number modulo 10^9+7.

EXPLANATION:

It is a 2x2 matrix A with A[0][0]=1, A[0][1]=1, A[1][0]=1, A[1][1]=0. With this matrix form one can calculate the nth

Fibonacci just by raising the matrix to the power n. A[0][1] will give you the nth Fibonacci number.

How to find the answer modulo 10^9+7.

Use the Binary Exponentiation technique. If the number becomes greater than 10^9+7 after the multiplication

then the elements of the matrix is replaced by their modulo 10^9+7.

Click [here](http://www.geeksforgeeks.org/program-for- nth-fibonacci- number/) for more details.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

//