### tweety's blog

By tweety, history, 6 years ago, 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  Comments (9)
 » 6 years ago, # | ← Rev. 5 →   Note that Application 3 is a special case of linear homogeneous recurrences relations with constant coefficients. If we have an order k relation of this kind: an = b0 * an - 1 + b1 * an - 2 + ... + bk - 1 * an - k Where bi are the constant coefficients, and the first k ai terms are known. We can find the n-th term of the recurrence applying matrix exponentiation. First, lets call A a companion matrix: If we multiply this matrix with a vector, whose elements are the first k known terms, we should obtain: Now, if we need to obtain an we can apply matrix exponentiation: For example, to find the 4-th term of the recurrence an = 2 * an - 1 + 3 * an - 2 + an - 3 With a0 = 1, a1 = 2, a2 = 4 As we can see, a3 = 2 * 4 + 3 * 2 + 1 * 1 = 15 a4 = 2 * 15 + 3 * 4 + 1 * 2 = 44 a5 = 2 * 44 + 3 * 15 + 1 * 4 = 137 a6 = 2 * 137 + 3 * 44 + 1 * 15 = 421
•  » » The correct term for it is a companion matrix, not a recurrence matrix.
•  » » » Right! Thanks!
 » For the second application you can get the minimum cost after maximum b steps by making M1[i][i] = 0 for every (1 <= i <= n).
 » Trying to solve the 2nd problem Getting TLE on 31st test case Complexity is N^3 log(N) Log N for binary search Question: 147B Submission: Link Any idea of how to remove TLE?
•  » » 3 years ago, # ^ | ← Rev. 5 →   Reason: if function requests T as argument there will be copy constructor call. In your sumbmission each call of mull, func, check_matrix will lead to copying matrix, which is extra $O(n^2)$. Solution:You really need create new matrix only as output of mull(). So you need:mull(int, const vector&, const vector&),func(ll, const vector&, const vector, ll),check_matrix(ll, const vector&) const T& tells that argument will be passed as reference to object, not copy. So there won't extra time. But within function you can't call any non-const method of argument. You also can rewrite func from recursive to iterate. This can decrees time too. P.S. Also your check functions is $O(n)$. Maybe you can leave this? Otherwise your solution would be $O(n^4logN)$. P.P.S. Forget it your complexity is $O(N^3log^2N)$ — first log for binary search, second log for multiplication. Maybe just your solution is wrong :).
•  » » » My new submission I know my solution is of N^3 (logN)^2. But this complexity solution passes Like this submission Solution with same complexity passes Any idea how?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   Don't sure, but there is some memorization. AC solution precalculates all powers $MTRX^{2^i}, i = 0..log(n)$. if $power = 41$ there will be: $res = MTR * MTR^8 * MTR^32$. — 3 multiplications. In your variant it's: $res = MTR * MTR^40 = MTR * (MTR^20)^2 = MTR * ((MTR^10)^2)^2 = MTR * (((MTR^5)^2)^2)^2 = MTR * (((MTR * MTR^4)^2)^2)^2 = MTR * (((MTR * MTR^2^2)^2)^2)^2$. — 7 multiplications. So in your solution there are some extra work with same complexity.
•  » » » » » Yeah Got it:) Submissions uses different way of applying binary search Thanks