tweety's blog

Cool tricks using Matrix Exponential
By tweety, history, 9 years ago, In English

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

  • Vote: I like it
  • +39
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
← Rev. 5   Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it +3 Vote: I do not like it

    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<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 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 :).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah Got it:) Submissions uses different way of applying binary search Thanks

          → Reply