# 1. Preface

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

# 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 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()
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
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:

$\begin{bmatrix}F_1&F_2\end{bmatrix}\begin{bmatrix}0&1\\1&1\end{bmatrix}^{n-2}$

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.

Posted by digitalecartoons on Sun, 17 Apr 2022 17:03:50 +0930