Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

tweety's blog

By tweety, history, 4 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

• +39

 » 4 years ago, # | ← Rev. 5 →   +23 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 - kWhere 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 = 4As we can see, a3 = 2 * 4 + 3 * 2 + 1 * 1 = 15a4 = 2 * 15 + 3 * 4 + 1 * 2 = 44a5 = 2 * 44 + 3 * 15 + 1 * 4 = 137a6 = 2 * 137 + 3 * 44 + 1 * 15 = 421
•  » » 4 years ago, # ^ |   +3 The correct term for it is a companion matrix, not a recurrence matrix.
•  » » » 4 years ago, # ^ |   0 Right! Thanks!
 » 4 years ago, # |   0 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).
 » 10 months ago, # |   0 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?
•  » » 10 months ago, # ^ | ← Rev. 5 →   +3 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 :).
•  » » » 10 months ago, # ^ |   0 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?
•  » » » » 10 months ago, # ^ | ← Rev. 3 →   +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.
•  » » » » » 10 months ago, # ^ |   0 Yeah Got it:) Submissions uses different way of applying binary search Thanks