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

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

Note that Application 3 is a special case of linear homogeneous recurrences relations with constant coefficients. If we have an

order krelation of this kind:a_{n}=b_{0}*a_{n - 1}+b_{1}*a_{n - 2}+ ... +b_{k - 1}*a_{n - k}Where

b_{i}are the constant coefficients, and the first ka_{i}terms are known.We can find the n-th term of the recurrence applying matrix exponentiation.

First, lets call

Aa 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

a_{n}we can apply matrix exponentiation:For example, to find the 4-th term of the recurrence

a_{n}= 2 *a_{n - 1}+ 3 *a_{n - 2}+a_{n - 3}With

a_{0}= 1,a_{1}= 2,a_{2}= 4As we can see,

a_{3}= 2 * 4 + 3 * 2 + 1 * 1 = 15a_{4}= 2 * 15 + 3 * 4 + 1 * 2 = 44a_{5}= 2 * 44 + 3 * 15 + 1 * 4 = 137a_{6}= 2 * 137 + 3 * 44 + 1 * 15 = 421The correct term for it is a companion matrix, not a recurrence matrix.

Right! Thanks!

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?

Reason: if function requests

Tas argument there will be copy constructor call. In your sumbmission each call ofmull,func,check_matrixwill 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<vector>&, const vector<vector>&),func(ll, const vector<vector>&, const vector<vector>, ll),check_matrix(ll, const vector<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

funcfrom recursive to iterate. This can decrees time too.P.S. Also yourcheckfunctions 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?

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