内容介绍
本文大致介绍了一下矩阵的基本定义，以及矩阵乘法的用途。
听说《线性代数》这门课是教矩阵的，当然我还没学，那么没学怎么办呢，难道只能摆了吗（）。
别急，我也才刚入门，我们从最基本的开始。（如果你已经学会了，你可以根据左侧的目录自己跳着看）
矩阵的基本定义
我在一篇文章中看到这样一句话：矩阵的本质就是线性方程式，两者是一一对应关系。
具体是什么意思呢？由于我不是专业的,我就直接拿我参考的文献的例子来讲解了，如果感兴趣的话，可以自己去网上搜一下或者去看文章底部的参考文献。
$$\begin{cases}2x \ + y = 3 \\ 4x \ + \ 3y \ = 7\end{cases}$$
矩阵的最初目的，只是为线性方程组提供一个简写格式（抄的文献，如有不对，请指出）
$$\begin{pmatrix}2 \ 1 \\ 4 \ 3 \end{pmatrix} \begin{pmatrix}x \\ y \end{pmatrix} \ = \ \begin{pmatrix} 3 \\ 7 \end{pmatrix}$$
这么写出来，如果大家会矩阵乘法的话试一下就可以看出来下面的式子的计算过程其实就是上面的方程式。不会的话别急，我们下面慢慢来。
有三组未知数x,y,t，其中x和y的关系如下。
$$\begin{cases}a_{1,1}x_{1} \ + \ a_{1,2}x_{2} = y_{1} \\ a_{2,1}x_{1} \ + \ a_{2,2}x_{2} \ = y_{2}\end{cases}$$
$$\begin{pmatrix} a_{1,1} \ a_{1,2} \\ a_{2,1} \ a_{2,2}\end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2}\end{pmatrix} \ = \ \begin{pmatrix} y_{1} \\ y_{2}\end{pmatrix}$$
x和t的关系如下。
$$\begin{cases}b_{1,1}t_{1} \ + b_{1,2}t_{2} = x_{1} \\b_{2,1}t_{1} \ + \ b_{2,2}t_{2} \ = x_{2}\end{cases}$$
$$\begin{pmatrix} b_{1,1} \ b_{1,2} \\ b_{2,1} \ b_{2,2}\end{pmatrix}\begin{pmatrix} t_{1} \\ t_{2}\end{pmatrix} \ = \ \begin{pmatrix} x_{1} \\ x_{2}\end{pmatrix}$$
有了这两组方程式，就可以求y和t的关系。显然，我们只需要把x用t代掉即可。
用方程表示的话如下：
$$\begin{cases}a_{1,1}(b_{1,1}t_{1} \ + \ b_{1,2}t_{2}) \ + \ a_{1,2}(b_{2,1}t_{1} \ + b_{2,2}t_{2}) = y_{1} \\a_{2,1}(b_{1,1}t_{1} \ + \ b_{1,2}t_{2}) \ + \ a_{2,2}(b_{2,1}t_{1} \ + b_{2,2}t_{2}) = y_{2}\end{cases}$$
而用矩阵表示的话
$$\begin{pmatrix}a_{1,1} \ a_{1,2} \\ a_{2,1} \ a_{2,2} \end{pmatrix} \begin{pmatrix} b_{1,1} \ b_{1,2} \\ b_{2,1} \ b_{2,2}\end{pmatrix}\begin{pmatrix} t_{1} \\ t_{2}\end{pmatrix} \ = \ \begin{pmatrix} y_{1} \\ y_{2}\end{pmatrix}$$
再将上面用方程式表示的用矩阵表示一下就是
$$\begin{pmatrix} a_{1,1}b_{1,1} \ + \ a_{1,2}b_{2,1} \ a_{1,1}b_{1,2} \ + \ a_{1,2}b_{2,2} \\ a_{2,1}b_{1,1} + a_{2,2}b_{2,1} \ a_{2,1}b_{1,2} \ + \ a_{2,2}b_{2,2}\end{pmatrix}\begin{pmatrix} t_{1} \\ t_{2}\end{pmatrix} \ = \ \begin{pmatrix} y_{1} \\ y_{2}\end{pmatrix}$$
上下对比一下就能发现：
$$\begin{pmatrix}a_{1,1} \ a_{1,2} \\ a_{2,1} \ a_{2,2} \end{pmatrix} \begin{pmatrix} b_{1,1} \ b_{1,2} \\ b_{2,1} \ b_{2,2}\end{pmatrix} \ = \ \begin{pmatrix} a_{1,1}b_{1,1} \ + \ a_{1,2}b_{2,1} \ a_{1,1}b_{1,2} \ + \ a_{1,2}b_{2,2} \\ a_{2,1}b_{1,1} + a_{2,2}b_{2,1} \ a_{2,1}b_{1,2} \ + \ a_{2,2}b_{2,2}\end{pmatrix}$$
所以矩阵乘法的计算方式就出来了。（这里我抄一下oiwiki的公式）
矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。
假设 $A$ 为 $P \times M$ 的矩阵， $B$ 为 $M \times \ Q $ 的矩阵，设矩阵$C$ 为矩阵 $A$ 与 $B$的乘积。
那么其中矩阵 $C$中的第 $i$ 行第$j$ 列元素可以表示为：
$$ C_{i,j} = \sum_{k=1}^{M} A_{i,k} B_{k,j} $$
这里的$C$的大小是 $P \times Q$
既然我们知道了矩阵实际上是线性方程式的另一种表达，那么我们也可以很方便的理解它的几何意义了，我们只需要把它放进一个坐标系就可以了。（由于实力有限，不过多展开）。
矩阵乘法的性质
既然我们都说它是乘法了，那么显然它是具有乘法的一些性质的。
例如，矩阵乘法满足乘法结合律，乘法分配律。（不满足交换律，因为要求有上文中列数与行数相同的性质）
同时快速幂在矩阵乘法上也是使用的。（节约篇幅，建议百度一下，或者等我以后补一篇快速幂）
矩阵乘法的应用
基本应用
简单来说，矩阵乘法可以加速递推公式，把$O(n)$的式子优化到 $O(logn)$
具体举例： 求斐波那契数列
$$f(n)=f(n-1)+f(n-2) \ \ n\geq 2$$
当$n$很大时（比如说大于$10^8$），我们直接使用递推是显然不可以的。这里我们需要考虑把递推式改成矩阵的形式。考虑到与前两项有关，我们构造一个$1 \times 2 $的矩阵$[F_{n},F_{n-1}]$
显然我们需要这么转移：
$$[F_{n-1},F_{n-2}] -> [F_{n},F_{n-1}]$$
$$[F_{n-1},F_{n-2}] -> [F_{n-1} \times 1+F_{n-2} \times 1,F_{n-1} \times 1 + F_{n-2} \times 0]$$
那么就可以构造出中间的矩阵了。
$$\left[\begin{matrix}1 & 1 \\1 & 0 \end{matrix}\right]$$
可以带回去验证一下，即可发现成立。
$$[F_{n-1},F_{n-2}]\left[\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}\right] = [F_{n-1} \times 1+F_{n-2} \times 1,F_{n-1} \times 1 + F_{n-2} \times 0] = [F_{n},F_{n-1}]$$
然后再运用快速幂即可。
OK，最简单的矩阵乘法已经会用了，接下来我们来小小进阶一下。
拓展应用
加法
$A$是一个矩阵，设矩阵$S$
$$S=A+A^{2}+A^{3}+…+A^{n} \ \ \ (n < 10^9)$$
那么我们要怎么求$S$，呢，显然，因为n很大，所以我们不能单纯的用矩阵乘法计算$A^n$然后再加起来。我们可以发现$S$ 实际上是一个等比数列的前缀和。如果我们直接套用等比数列的求和公式的话，显然:
$$S=\frac{A \times (1-A^n)}{1-A}$$
我并不会算$\frac{1}{1-A}$，也就是说我无法将逆矩阵算出来，并且有些矩阵是没有逆矩阵的，所以说这种方法是不可行的。所以我们要考虑另外一种方法来做出这道题。
对于等比数列，我们没有别的性质可以使用了。接下来就剩下前缀和的性质了。我们可以设
$$B_{n}=A^{n}$$
$$S_n=B+B_{2}+B_{3}+…+B_{n}$$
根据前缀和的性质，显然$S_n=S_{n-1}+B_{n}$
可以发现这是一个递推式，所以，我们就可以用矩阵乘法来处理这个递推式。
由于我们要用到$S_{n-1}$和$B_{n}$这两个量来实现递推，所以我们可以用和上面推斐波那契的矩阵一样。
$$[S_{n-1},A_{n}] ->[S_{n},A_{n+1}]$$
$$[S_{n-1},A_{n}] -> [S_{n-1} \times 1+A_{n} \times 1,S_{n-1} \times 0 + A_{n} \times A]$$
所以我们照样可以构造出中间的矩阵：
$$\left[\begin{matrix}1 & 1 \\0 & A \end{matrix}\right]$$
带回去即可发现成立。
$$[S_{n},A_{n+1}]=[S_{n-1},A_{n}]\left[\begin{matrix}1 & 0 \\1 & A \end{matrix}\right]=[0,A]\left[\begin{matrix}1 & 0 \\1 & A \end{matrix}\right]^{n}$$
那么我们就可以用矩阵快速幂快速的算出最后的答案了。那么显然，对于任何样子的递推式都可以通过矩阵快速幂来加速。
当然，这一题不止这么一种解题方法，但是我自己是使用的这一种，应该是一种通法，只要是递推式都可以用。（我代码里用的板子是oi-wiki里的）
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;
const int N=40;
int n,k,m;
struct mat{
long long a[N][N];
mat(){memset(a,0,sizeof a);}
mat operator+(const mat& T) const {
mat res;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
res.a[i][j]=(a[i][j]+T.a[i][j])%m;
}
}
return res;
}
mat operator*(const mat& T) const {
mat res;
int r;
for(int i=1;i<=n;i++){
for(int k=1;k<=n;k++){
for(int j=1;j<=n;j++){
res.a[i][j]=res.a[i][j]+a[i][k]*T.a[k][j],res.a[i][j]%=m;
}
}
}
return res;
}
}A;
struct Mat{
mat a[3][3];
Mat operator+(const Mat& T) const {
Mat res;
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
res.a[i][j]=(a[i][j]+T.a[i][j]);
}
}
return res;
}
Mat operator*(const Mat& T) const {
Mat res;
int r;
for(int i=1;i<=2;i++){
for(int k=1;k<=2;k++){
for(int j=1;j<=2;j++){
res.a[i][j]=res.a[i][j]+a[i][k]*T.a[k][j];
}
}
}
return res;
}
}mid;
Mat qmi(Mat a,long long b){
Mat res;
for(int i=1;i<=2;i++){
for(int j=1;j<=n;j++){
res.a[i][i].a[j][j]=1;
}
}
while(b){
if(b&1) res=res*a;
b>>=1;
a=a*a;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k>>m;
mat danwei;
for(int i=1;i<=n;i++){
danwei.a[i][i]=1;
for(int j=1;j<=n;j++){
cin>>A.a[i][j];
}
}
mid.a[1][1]=danwei;
mid.a[2][1]=danwei;
mid.a[2][2]=A;
mid=qmi(mid,k);
Mat chushi;
chushi.a[1][2]=A;
Mat ans;
for(int i=1;i<=1;i++){
for(int j=1;j<=2;j++){
for(int k=1;k<=2;k++){
ans.a[i][j]=ans.a[i][j]+chushi.a[i][k]*mid.a[k][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<ans.a[1][1].a[i][j]<<' ';
}
cout<<'\n';
}
}乘法递推
写题的时候又看到一道题的递推式是乘法递推，当时没想出来怎么写，现在再在这里记录一下。
下面是例题$(n \leq 10^{12})$：
$$a_{n}=a_{n-1} \times a_{n-2}$$
$$a_{1}=a_{1}$$
$$a_{2}=a_{2}$$
$$a_3=a_{1} \times a_{2}$$
$$a_{4}=a_{1} \times a_{2}^2$$
$$a_{5}=a_{1}^2 \times a_{2}^3$$
$$a_{n}=a_{1}^{fic(n-2)} \times a_{2}^{fic(n-1)} (n >2)$$
那么只需要对指数上的斐波那契函数用矩阵快速幂求即可。
卡常技巧
有点懒了，不想抄了，想看的话可以直接去看参考文献第一条，我就不抄了，有点多。
模版
我这里直接把oi-wiki里的模版放在这里了，大家可以根据不同情况灵活运用。
我本人本来是想直接写函数来实现矩阵乘法的，奈何我并不会用指针，无法满足在函数结束时返回数组（即矩阵）。后来我观察模版，可以通过返回结构体的方式返回矩阵。所以我觉得这个模版还是有点借鉴意义的。
struct mat {
LL a[sz][sz];
mat() { memset(a, 0, sizeof a); }
mat operator-(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) {
res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
}
return res;
}
mat operator+(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) {
res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
}
return res;
}
mat operator*(const mat& T) const {
mat res;
int r;
for (int i = 0; i < sz; ++i)
for (int k = 0; k < sz; ++k) {
r = a[i][k];
for (int j = 0; j < sz; ++j)
res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
}
return res;
}
mat operator^(LL x) const {
mat res, bas;
for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
while (x) {
if (x & 1) res = res * bas;
bas = bas * bas;
x >>= 1;
}
return res;
}
};参考文献
好多卡常的技巧
零基础认识一下矩阵乘法
模版
