tl;dr — video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.com/gym/102644 (register by finding this contest in GYM instead of using the link directly)
video editorial: part 1 (ABCDEF) and part 2 (GHI)
codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation
Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices)
The youtube tutorial (link) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead. You can practice by solving a set of 9 educational problems in GYM https://codeforces.com/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis — part 1 (ABCDEF) and part 2 (GHI).
Hints
C. FibonacciYou need to first solve a problem with dp in $$$O(1)$$$ space. Here are two such codes:
code1int n;
cin >> n;
int a = 0, b = 1;
for(int i = 2; i <= n; i++) {
int new_a = 0 * a + 1 * b;
int new_b = 1 * a + 1 * b;
a = new_a;
b = new_b;
}
cout << a << " " << b << endl;
code2int n;
cin >> n;
int arr[2] = {0, 1};
for(int i = 2; i <= n; i++) {
int new_arr[2] = {0, 0};
new_arr[0] = 0 * arr[0] + 1 * arr[1];
new_arr[1] = 1 * arr[0] + 1 * arr[1];
arr[0] = new_arr[0];
arr[1] = new_arr[1];
}
cout << arr[0] << " " << arr[1] << endl;
D. Count PathsIn the first youtube video, there is graph-like visualization of the String Mood problem, it's the same thing here. A cell of matrix $$$m[i][j]$$$ should keep the number of paths from vertex $$$i$$$ to vertex $$$j$$$.
E. Knight PathsSame as the previous problem but we allow any length up to $$$k$$$. Try to solve it with dp in $$$O(64)$$$ space and create an array with ALL variables you need to maintain.
F. Min PathMatrix exponentiation isn't just for summing up products of values in some cells. Just define $$$m[i][j]$$$ as the shortest path from vertex $$$i$$$ to vertex $$$j$$$. The function for "multiplication of two matrices" will slightly change.
G. Recurrence With SquareTry to do it first for $$$q = r = 0$$$ and then for $$$r = 0$$$.
This is a much harder version of problem E, where we already needed to express space-efficient dp in a particular way.
When doing space-efficient dp, avoid using index $$$i$$$ from a for-loop. We can use matrix exponentiation only if there is some constant matrix (two-dimensional array of transition) to be applied $$$k$$$ times.
int variable_array[...]; // create all variables you need
for(int _ = 0; _ < k; _++) {
do something; // don't use the underscore variable
}
H. String Mood UpdatesThis problem doesn't require binary exponentiation but it still involves matrices.
What is often used in cp problems with updates in a sequence?
I. Count Paths QeuriesIf you do matrix exponentiation for every query, that's $$$O(q \cdot n^3 \cdot \log k)$$$, too slow.
Precompute $$$M^1, M^2, M^4, M^8, \ldots$$$ — matrices with counts of paths of length being a power of $$$2$$$. After this preprocessing, try to answer queries without any multiplication of two matrices. Can you use preprocessed matrices to answer e.g. $$$k = 6$$$ in $$$O(n^2)$$$?
Matrix Exponentiation
Consider this problem:
String Mood — Limak can be either happy or sad. His mood changes (or stays same) when he reads an English uppercase letter. Letters S and D always make him sad, H makes him happy, and every vowel (AEIOU) flips his mood. Other letters do nothing.
Limak is happy right now. Among all $$$26^n$$$ possible strings of length $$$n$$$ ($$$n \leq 10^{18}$$$), count such strings that Limak will be happy after reading that string, modulo $$$10^9+7$$$.
If something can be solved with dp in $$$O(1)$$$ space, we can usually speed it up later with matrix exponentiation. This dp is easy — for length from $$$1$$$ to $$$n$$$ compute the number of strings making you happy and making you sad at the end.
dp in O(1) space#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main() {
long long n;
cin >> n;
long long happy = 1, sad = 0;
for(long long i = 0; i < n; ++i) {
long long new_happy = (19 * happy + 6 * sad) % mod; // 19 letters will keep you happy, etc.
long long new_sad = (7 * happy + 20 * sad) % mod;
happy = new_happy;
sad = new_sad;
}
cout << happy << endl;
}
Let's visualize that by drawing vertices representing the two moods, and edges with the number of ways to move from one state to the other.
For example, if you are happy, there are 19 ways to make you happy and 7 ways to make you sad (SDAEIOU). Thin edges on the right represent the second letter of a string and the number there should be the same, because they are again 19 ways to make you happy if you were happy, etc. If we were asked about answer for $$$n = 2$$$, we would need to compute the number of ways to get from HAPPY state in first column to HAPPY state in third column, which is they yellow edge below.
That's $$$19 \cdot 19 + 7 \cdot 6 = 403$$$. In a similar way, we can compute all four counts for 2-letter strings: happy to happy (equal to $$$403$$$), happy to sad ($$$19\cdot7+7\cdot20=273$$$), sad to happy ($$$234$$$), sad to sad ($$$442$$$). We'll actually keep these four values $$$ [ [403,273], [234, 442] ] $$$ in a 2-dimensional array, also called a matrix.
Starting from a matrix with four values describing 1-letter strings $$$[ [19,7],[6,20] ]$$$, in $$$O(1)$$$ we got a matrix describing 2-letter strings. We can do the same to get a matrix for 4-letter strings, then 8-letter strings, and so on. We can do binary exponentiation to find a matrix for any huge $$$n$$$. Formally, we compute $$$M^n$$$ where $$$M = [ [19,7],[6,20] ]$$$ and multiplying two matrices is exactly what we did above to compute a new matrix $$$[ [403,273],[234, 442] ]$$$, done with the following code:
for(int i = 0; i < s; i++) { // s is the number of states, s=2 in the String Mood problem
for(int j = 0; j < s; j++) {
for(int k = 0; k < s; k++) {
new_matrix[i][k] += matrix1[i][j] * matrix2[j][k];
}
}
}
The total time complexity is $$$O(s^3 \cdot \log n)$$$ where $$$s$$$ is the matrix size (also called order), which is equal to the number of states (variables) you need in space-efficient dp. We had $$$s=2$$$ in String Mood so the complexity is just $$$O(\log n)$$$.
full C++ solution#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
#define REP(i, n) for(int i = 0; i < (n); i++)
struct Matrix {
long long a[2][2];
Matrix() {
REP(i, 2) {
REP(j, 2) {
a[i][j] = 0;
}
}
}
Matrix operator *(Matrix other) {
Matrix product = Matrix();
REP(i, 2) {
REP(j, 2) {
REP(k, 2) {
product.a[i][k] += a[i][j] * other.a[j][k];
product.a[i][k] %= mod;
}
}
}
return product;
}
};
Matrix expo_power(Matrix a, long long n) {
Matrix res = Matrix();
res.a[0][0] = res.a[1][1] = 1;
while(n) {
if(n % 2) {
res = res * a;
}
n /= 2;
a = a * a;
}
return res;
}
int main() {
long long n;
cin >> n;
Matrix single = Matrix();
single.a[0][0] = 19;
single.a[0][1] = 7;
single.a[1][0] = 6;
single.a[1][1] = 20;
Matrix total = expo_power(single, n);
cout << total.a[0][0] << endl;
}
Now, try to find the $$$n$$$-th Fibonacci number for $$$n \leq 10^{18}$$$ (problem link) by first implementing space-efficient dp with transitions of form new_variable += old_variable * x
where $$$x$$$ is some number you will need to put in the initial matrix (like $$$19$$$ or $$$7$$$ in String Mood).
Footnote
Thanks to tnowak for suggesting and creating one problem, and to mnbvmar for a few problem ideas. For the future, I'm looking for somebody to help me with the preparation of such training contests. If you want to help and you are high-rated and perfectly with experience in using polygon, please write to me. I can pay you a little if you want.
I hope you learned something thanks to this tutorial. Feel free to discuss problems from the GYM contest or give links to more matrix exponentiation problems or useful resources. If anybody wants that, I can make tests public. If you are a teacher and want to use some problems in your classes, I will give you access in Polygon.