矩阵是计算机数学里一个比较重要的内容，它可以优化很多地方的推导，这里简要地总结一下
形如\[\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}\quad\] 或\[\begin{bmatrix} a_1 & a_2 & a_3\\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \end{bmatrix}\quad\] 通用形式\[\begin{bmatrix} a_1 & a_2 & …… & a_n \\ b_1 & b_2 & …… & b_n \\ …… & …… & …… & ……\\ z_1 & z_2 & …… & z_n\end{bmatrix}\quad\] 这就是矩阵 简单点来说，就是一个二维数组
说完了矩阵，那么什么是矩阵乘法呢？
首先说明一点，矩阵乘法A*B要求满足A的行数等于B的列数!,这是由矩阵乘法的运算性质来的。 我们设A*B=T（三个都是矩阵），那么对于T[i][j]来说，\[T[i][j]=\Sigma(A[i][k]*B[k][j])\] 举个例子\[\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}* \begin{bmatrix} 10 & 11 & 12 \\ 13 & 14 & 15 \\ 16 & 17 & 18 \end{bmatrix}=\begin{bmatrix} 1*10+2*13+3*16 & 1*11+2*14+3*17 & 1*12+2*15+3*18 \\ 4*10+5*13+6*16 & 4*11+5*14+6*17 & 4*12+5*15+6*18 \\ 7*10+8*11+9*16 & 7*11+8*14+9*17 & 7*12+8*15+9*18\end{bmatrix}\] （写得有点长，仔细阅读后可以找到规律） 用字母表示就是\[\begin{bmatrix} a & b & c\\ d & e & f \\ g & h & i \end{bmatrix}*\begin{bmatrix} j & k & l \\ m & n & o \\ p& q & r\end{bmatrix}=\begin{bmatrix} aj+bm+cp & ak+bn+cq & al+bo+cr \\ dj+em+fp & dk+en+fq & dl+eo+fr \\ gj+hm+ip & gk+hn+iq & gl+ho+ir \end{bmatrix}\] 说的通俗一点，结果矩阵的第i行第j列等于矩阵A第i行与矩阵B第j列分别乘积的和（现在明白为什么矩阵乘法要求A的行数与B的列数相同了吧，因为要保证有东西乘，若不相等会导致缺少一些项）
如果要求数字X的k次方，我们该如何求呢？ 最简单的方法就是用一个循环，循环k次，每次相乘。 但这样效率太低，下面来介绍一下快速幂的方法。 我们知道，任何一个十进制的数都可以表示成为二进制的形式，比如12转成二进制就是1100,这同样也表示\[12=2^3+2^2\] 那么对于任意一个数k，它就可以表示为：\[k=2^{a_1}+2^{a_2}+……+2^{a_n}\] 而我们又知道：\[x^{2^i}=(x^{2^{i-1}})^2\] 这就可以加速我们的幂运算，下面先给出代码：
int pow(int x,int k) { int ans=1; int res=x; while (k>0) { if (k%2==1) ans=ans*res; res=res*res; k=k/2; } return ans; }解释一下，ans就是最后我们返回的x^k的值，而res则是一个累乘器，它基于的原理就是上面给出的\[x^{2^i}=(x^{2^{i-1}})^2\] 当然，上面这个代码还不是最快的，还可以用位运算优化一下
int pow(int x,int k) { int ans=1; int res=x; while (k>0) { if (k&1) ans=ans*res; res=res*res; k=k>>1; } return ans; }把快速幂与矩阵乘法相结合就是矩阵快速幂，其中快速幂的过程并不需要修改，只要定义一个关于矩阵的结构体并重载一下乘法运算符就可以了,为了方便运算，同时尽量满足矩阵乘法的性质，下面的矩阵都是n*n的。
class Matrix { public: int n;//n是当前矩阵的大小 int A[maxN][maxN];//maxN就是矩阵的最大大小 Matrix()//初始化矩阵中的所有元素都为０ { memset(A,0,sizeof(A)); } } Matrix operator * (Matrix A,Matrix B)//重载乘法运算 { Matrix Ans; int size=A.n; Ans.n=size; for (int i=0;i<size;i++) for (int j=0;j<size;j++) for (int k=0;k<size;k++) Ans.A[i][j]+=A.A[i][k]*B.A[k][j]; return Ans; }这个有什么用呢，我们下面再说。
利用矩阵，我们可以优化许多有关于递推和动态规划的问题。 我们先看一个简单的例子：斐波那契数列 我们知道斐波那契数列的递推式是\[F[i]=F[i-1]+F[i-2]\] 但是这样递推在i很大的时候效率不高，并且若不用滚动操作，空间消耗也很大。 （你说用通项公式？抱歉，无理数的精度是个问题） 我们考虑如何用矩阵来优化。 什么意思，就是我们希望得到一个式子满足F[i]=A*A[i-1]，这样我们就可以直接得到直接求出F[n]的式子，\[F[n]=F[1]*A^{n-1}\] 再结合快速幂，我们就可以快速解决了。 先别急，我们先想一想我们需要那些状态。 要求出f[i]（注意，这里我们开始用小写，因为我们用大写表示矩阵，而用小写表示原来的递推式中的元素），我们至少需要知道f[i-1]和f[i-2]的信息，所以我们可以列出下面这样的信息矩阵：\[F[i-1]=\begin{bmatrix} f[i-1]&f[i-2]\end{bmatrix}\] 我们再看一看我们要得到怎样的目标状态呢？ 直接看f[i+1]需要那些元素，很明显，f[i+1]由f[i]和f[i-1]推来，所以我们可以列出下面的目标矩阵:\[F[i]=\begin{bmatrix} f[i] & f[i-1] \end{bmatrix}\] 根据斐波那契数列的普通递推式，我们又可以把上面这个矩阵表示成为下面这种形式：\[F[i]=\begin{bmatrix} f[i-1]+f[i-2] & f[i-1] \end{bmatrix}\] 现在的任务就是要找出一个一个矩阵Ｔ使得F[i-1]*T=F[i] 根据矩阵乘法的运算法则，我们可以得出这个矩阵T:\[F[i]=F[i-1]*T=\begin{bmatrix} f[i-1]&f[i-2]\end{bmatrix}*\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}=\begin{bmatrix} f[i-1]+f[i-2] & f[i-1] \end{bmatrix}\] （这里推荐读者手动计推算一下） 当然，为了方便运算，这里我们把矩阵都补成正方形，方便存储和运算\[F[i]=F[i-1]*T=\begin{bmatrix} f[i-1]&f[i-2]\\ 0 & 0 \end{bmatrix}*\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}=\begin{bmatrix} f[i-1]+f[i-2] & f[i-1] \\ 0 & 0 \end{bmatrix}\] 有了转移矩阵T，我们就可以用快速幂迅速求出斐波那契数列的任意一项了。
下面给出一些矩阵乘法优化的题目，它们都是一些递推的题目，但加强了数据范围，读者可以去熟悉矩阵的相关计算Luogu 3390 【模板】矩阵快速幂 （矩阵乘法，快速幂）（一道矩阵快速幂模板题）
Luogu 1962 斐波那契数列（矩阵，递推）（就是文章中那个斐波那契数列的例子）
Luogu 1349 广义斐波那契数列（递推，矩阵，快速幂）（斐波那契数列的加强版，不再是简单的f[i]=f[i-1]+f[i-2]，而是f[i]=a*f[i-1]+b*f[i-2]，并且初始值f[1]和f[2]也是给定的）
Luogu T7152 细胞（递推，矩阵乘法，快速幂）（稍微复杂点的用矩阵优化的递推）
CJOJ 1331 【HNOI2011】数学作业 / Luogu 3216 【HNOI2011】数学作业 / HYSBZ 2326 数学作业（递推，矩阵）（HNOI往年省选题，需要特殊处理的矩阵快速幂） 更多题目可以到右侧我的随笔分类中数学---矩阵中查看
转载于:https://www.cnblogs.com/SYCstudio/p/7211050.html
