Matrix Exponentiation

This is very easy and frequently used topic in competitive programming.

If studied correctly you don’t have learn the code you can write its code in minutes.

This is a step-wise guide for matrix exponentiation.

Why do we need Matrix Exponentiation method

If you have to solve a recurrence relation of the type

F(n)=F(n-1)+F(n-2)+F(n-3)+…….. and so on upto a specific point

With n <=10^18

For example if

Relation i-
1.) F(n)=F(n-1)+F(n-2)

It is the Fibonacci series.

1.) F(n)=F(n-1)+F(n-2)+F(n-3)

Tribonacci series.

Matrix exponentiation can be used to solve such series/recurrence relations very fastly.

Let’s get started