Part of course:

Tutorial: Matrix Exponentiation

NaN.

Part of course: Competitive Programming: From Beginner to Expert

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.

**This video** shows how to find the n-th term of any linear recurrence relation (where n is very large ~10^18) . You should be able to understand the technique after watching these videos.

**Problem** : Problem SEQ

**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…(173 words)

Mark as completed

Previous

All Pairs Shortest Path (Floyd Warshall)

Next

[MPOW] Power of matrix

Part of courses:

About the contributors:

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

63%

Mohit Raihttps://www.youtube.com/c/Gocode

37%

Loading…

Have a question? Ask here…

Post

Part of course:

Tutorial: Matrix Exponentiation

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons 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.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.