I'm going to share with you some cool applications of matrix exponential that I learned recently.
Application 1: Counting the number of ways for reaching a vertex
You are given an unweighted directed graph (may contain multiple edges) containing N vertices (1 <= N <= 200) and an integer b (1 <= b <= 10^9). You are also given Q queries (1 <= Q <= 10^5). For each query you are given two vertices u and v and you have to find the number of ways for reaching vertex v starting from u after b steps. (A step is passing through an edge. Each edge may be passed multiple number of times).
Solution
Let M1 be a matrix where M1[i][j] equals the number of edges connecting vertex i to vertex j. Let M2 be M1 raised to the power of b (M1^b). Now for any pair u and v, the number of ways for reaching vertex v starting from u after b steps is M2[u][v].
Practice problem: 621E
Application 2: Shortest path with a specified number of steps
You are given a weighted graph containing N vertices (1 <= N <= 200) and an integer b (1 <= b <= 10^9). You are also given Q queries (1 <= Q <= 10^5). For each query you are given two vertices u and v and you have to find the minimum cost for reaching vertex v starting from u after exactly b steps. (A step is passing through an edge. Each edge may be passed multiple number of times).
Solution
Let M1 be a matrix where M1[i][j] equals the cost of passing the edge connecting i to j (infinity if there is no edge). Let M2 be M1 raised to the power of b (but this time using the distance product for multiplication). Now for any pair u and v, the minimum cost for reaching vertex v starting from u after b steps is M2[u][v].
Practice problem: 147B
Application 3: Nth Fibonacci number in O(log n)
You are given Q (1 <= Q <= 10^5) queries. For each query you are given an integer N (1 <= N <= 10^9) and you are to find the Nth number in the Fibonacci sequence.
Solution
I won't copy-paste anything, you can read about it here.
In case you don't know how to multiply matrices, you can read about it here. After you know how to multiply matrices you can easily calculate the power of a matrix in O(log n) just like you do with integers.
Any corrections/suggestions/additions are welcome.
And please point out any English mistakes or sentences that can be improved. :D
