Rare

0/6

Matrix Exponentiation

Author: Benjamin Qi

Prerequisites

Gold - Introduction to DP

Repeatedly multiplying a square matrix by itself.

Edit with LiveUpdate

Resources
CP2	5.9 - Powers of a Square Matrix
CPH	23 - Matrices
CF	Errichto - Matrix Exponentiation	video + problemset
CF	Cool tricks using Matrix Exponential	interesting applications of mat exp
Mostafa	Matrix Power Applications	powerpoint of matrix exponentiation

Problems

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	CSES	Fibonacci Numbers	Easy	Show Tags Exponentiation, Matrix	CPH 23.2
	CSES	Graph Paths I	Easy	Show Tags Exponentiation, Matrix	CPH 23.3
	CSES	Graph Paths II	Easy	Show Tags Exponentiation, Matrix	CPH 23.3
	Baltic OI	2007 - Connected Points	Easy	Show Tags Exponentiation, Matrix	External Sol
	Balkan OI	2009 - Reading	Normal	Show Tags Exponentiation, Matrix	External Sol
	Plat	COWBASIC	Hard	Show Tags Exponentiation, Matrix	External Sol

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!