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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s