Cool tricks using Matrix Exponential

Revision en2, by tweety, 2016-02-20 01:40:57

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 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 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

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.

And please point out any English mistakes or sentences that can be improved. :D #### History

Revisions Rev. Lang. By When Δ Comment
en2 tweety 2016-02-20 01:40:57 8 Tiny change: 'm u after b steps. ' -> 'm u after exactly b steps. '
en1 tweety 2016-02-20 01:15:11 2875 Initial revision (published)