1. Preface

This article is the author's notes when learning matrix.

Note that the author is an OIer, so it does not involve professional knowledge of Linear Algebra (or very little).

Pre knowledge: Matrix definition + matrix multiplication，Fast power of positive integer.

2. Fast power of matrix

We know that there is a definition of power in the complex number (or simple point, real number):

For \ (a \in C \), record \ (a \ times a \ times... \ times a \) (of \ (n \)) as \ (a^n \).

Therefore, following this definition, the definition of power in the matrix is as follows:

For a matrix \ (a \) with the size of \ (k \times k \), record \ (AAAA...A \) (of \ (n \)) as \ (A^n \).

It should be noted that the number of rows and columns of \ (A \) should be the same, otherwise it does not meet the requirements of matrix multiplication.

Then let's calculate \ (A^n \), and the complexity is \ (O(k^3n) \).

Consider how to optimize it?

Recall the method of fast power of positive integers: using the combination law, tear down \ (B \) in \ (a^b \) according to binary bits, so as to achieve the complexity of \ (O(\log b) \).

Since the matrix also satisfies the binding law, we can also use the binding law to split the index \ (B \) into binary operations, so as to achieve the complexity of \ (O(k^3 \log b) \) (\ (K \) is the size of the matrix).

Template question link: P3390 [template] matrix fast power

Code:

/*
========= Plozia =========
    Author:Plozia
    Problem:P3390 [Template] matrix fast power
    Date:2021/6/1
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 100 + 10, P = 1e9 + 7;
int n;
LL k;

struct Matrix
{
    LL a[MAXN][MAXN];
    Matrix operator *(const Matrix &fir)
    {
        Matrix c; memset(c.a, 0, sizeof(c.a));
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k <= n; ++k)
            {
                int r = a[i][k];
                for (int j = 1; j <= n; ++j) { c.a[i][j] += r * fir.a[k][j]; c.a[i][j] %= P; }
            }
        return c;
    }
}a;

LL Read()
{
    LL sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }

Matrix ksm(Matrix a, LL b, LL p)
{
    Matrix ans;
    for (int i = 1; i <= n; ++i)
            ans.a[i][i] = 1;
    for (; b; b >>= 1, a = a * a)
        if (b & 1) ans = ans * a;
    return ans;
}

int main()
{
    n = Read(), k = Read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            a.a[i][j] = Read();
    Matrix ans = ksm(a, k, P);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j) printf("%lld ", ans.a[i][j]);
        printf("\n");
    }
    return 0;
}

3. Examples

A very important application of fast power of matrix is fast recursion.

for instance: P1962 Fibonacci sequence

If the direct recursive \ (O(n) \) method is adopted, a good result of 60pts will be obtained.

So how to get 100pts? At this time, the matrix is needed.

From the formula \ (f _n = f {n-2} + F {n-1} \), we can construct a matrix \ (\ begin {bMatrix} f {n-1} & F N \ end {bMatrix} \), and the matrix to be derived is \ (\ begin {bMatrix} f {n} & F {n + 1} \ end {bMatrix} \).

Make a deformation of the matrix to be launched: \ (\ begin {bMatrix} 0 \ times f {n-1} + 1 \ times f {n} & 1 \ times f {n-1} + 1 \ times f {n} \ end {bMatrix} \).

So we can construct such a transfer matrix: \ (\ begin {bMatrix} 0 & 1 \ \ 1 & 1 \ end {bMatrix} \).

So \ (\ begin {bMatrix} f {n-1} & F {n \ end {bMatrix} \ begin {bMatrix} 0 & 1 \ \ 1 & 1 \ end {bMatrix} = \ begin {bMatrix} f {n} & F {n + 1} \ end {bMatrix} \)

Now we know the initial state matrix \ (\ begin {bMatrix} f_1 & f_2 \ end {bMatrix} \), so if we ask for the value of \ (F_n(n \geq 3) \), we can calculate the following result and take the second element:

It is found that this can be quickly optimized by matrix power.

Note that when \ (n < 3 \), directly output \ (f {n} \).

4. Summary

• Matrix fast power: use the combination law of matrix multiplication to reduce the complexity.
• Application: using matrix optimization formula to add fast recursion.