矩阵运算是一类特殊而且有意思的运算方式,有的特殊矩阵甚至可以视为向量
这次我们来介绍一下矩阵加法和乘法.

基本内容

矩阵加法:只有规格相同的矩阵才能相加,相加的结果仍然是规格相同的矩阵,矩阵中的元素为两个矩阵中对应元素相加,并不难理解,于是不再多说.

重点是矩阵乘法

矩阵乘法的适用同样有条件,只能是$m\times n$和$n\times r(n,m,r\in N^*)$.在这里我决定先给出公式再解释.

$$
C_{i,j}=\sum_{k=1}^{n}A_{i,k}\times B_{k,j}
$$

这就是新矩阵的每一位元素的得出方法.接下来我来介绍我们是怎么定义这种计算的.矩阵乘法的第i行第j个元素就是第一个矩阵第i行所有元素分别乘上第二个矩阵第j列所有元素的值.我们之所以规定必须是$m\times n$和$n\times r$的矩阵相乘.是为了保证了第i行和第j列都有n个元素,能够一一对应才如此.

矩阵乘法有什么性质呢

首先也是最容易忽略的一条,它不满足交换律.从定义我们可以看出,在左边的矩阵提供提供行,右边的矩阵提供列.因此交换左右可能乘法甚至失去意义.不过它满足结合律.同时也满足左右分配律.

矩阵乘法有什么用呢?

它可以用来加速递推,最简单也是最经典的例子,它可以在$\Theta(log_2n)$的时间复杂度内求出斐波那契数列的第n项,现在我们来看一看这个例子.我们知道,斐波那契数列的递推公式是这样的:
$$ fib_i=
\begin{cases}
&1& &{i=0,1}\\
&fib_{i-1}+fib(i-2)& &{i\le 2}\\
\end{cases}
$$
前两位已经固定了,因此我们来研究后面的怎么办.我们可以构建一个矩阵
$\begin{bmatrix}fib_{i-1}\\fib_{i-2}\end{bmatrix}$,把它们装在矩阵里之后,我们的目标就是得到$\begin{bmatrix}fib_{i}\\fib_{i-1}\end{bmatrix}$我们可以尝试左乘或者右乘一个矩阵试试.我们发现,如果尝试右乘,将要乘一个$1\times 1$的矩阵,最后没法推出,除非我们把矩阵”横过来”.而左乘一个矩阵则可以.考虑我们要得到新矩阵,它的第一个元素是旧矩阵两个元素之和,第二个元素只是旧矩阵第一个元素.通过思考,我们可以构造出以下式子:
$$
\begin{bmatrix}1& 1\\1& 0\end{bmatrix}\times
\begin{bmatrix}fib_{i-1}\\fib_{i-2}\end{bmatrix}=
\begin{bmatrix}fib_{i}\\fib{i-1}\end{bmatrix}
$$
然而这只是实现了递推,为了超快求出第n项,我们还有一种神奇的方法:快速幂.

矩阵的快速幂是实现加速的核心.因为我们是通过乘以同一个矩阵多次才求出结果,因次可以通过将转移矩阵自身自乘多次来达到$\Theta(log_2n)$的复杂度.
接下来上代码(快速求$fib_{n}\ mod\ 1e9+7(n\le Max_longlong)$)

#include <cmath>
#include <queue>
#include <deque>
#include <cctype>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define mod 1000000007
using namespace std;

template<class T> inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch))
        w = (ch =='-'), ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int n, org[3] = {0, 1, 1};

struct matrix {
    int a[3][3];
    matrix() { memset(a, 0, sizeof(a)); }
    matrix operator * (const matrix &b) const {
        matrix res;
        for (int i = 1; i <= 2; ++i)
            for (int j = 1; j <= 2; ++j)
                for (int k = 1; k <= 2; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
        return res;
    }
};

matrix ans, base;

inline void quick_multrix(int times) {
    while (times) {
        if (times & 1)
            ans = ans * base;
        base = base * base;
        times >>= 1;
    }
    return;
}

signed main() {
    read(n);
    if (n <= 2) {
        cout << 1 << endl;
        return 0;
    }
    base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
    ans.a[1][1] = ans.a[1][2] = 1;
    quick_multrix(n - 2);
    cout << ans.a[1][1] % mod << endl;
    return 0;
}

——Gensokyo