Part of list:

Tutorial: Matrix Exponentiation

Tutorial: Matrix Exponentiation[ Edit ]

**Prerequisites**: Matrix in algebra, Matrix multiplication

**Introduction**: Matrix Exponentiation (also known as matrix power, repeated squaring) is a technique used to solve linear recurrences. This technique is very useful in competitive programming when dealing with linear recurrences (appears along Dynamic Programming). This technique also solves a lot of problems in graph theory. Only solving recurrences is covered here, applications on graph theory will be discussed later.

**Video tutorial**: This video shows how you can use matrices to calculate the n-th fibonacci number (where n is very large ~10^18). You should be able to understand the technique after watching this video. Exercises will be added soon.

**Text tutorial**: It's highly recommended to take a look at this tutorial by Fushar (even if you watched the video): Solving Linear Recurrence for Programming Contest.

Read more…(136 words)

Mark as completed

Part of lists:

Previous

All Pairs Shortest Path (Floyd Warshall)

Next

[MPOW] Power of matrix

About the contributor:

Hussain Kara FallahACM ICPC Contestant, Coach, Judge, Problem Setter. IOI 2014.

100%

Loading…

Have a question? Ask here…

Post

Part of list:

Tutorial: Matrix Exponentiation

Contributor

Hussain Kara FallahACM ICPC Contestant, Coach, Judge, Problem Setter. IOI 2014.

100%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.