矩阵是计算机数学里一个比较重要的内容,它可以优化很多地方的推导,这里简要地总结一下
形如
\[\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() //初始化矩阵中的所有元素都为0
- {
- 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}\]
现在的任务就是要找出一个一个矩阵T使得 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 往年省选题,需要特殊处理的矩阵快速幂)
来源: http://www.cnblogs.com/SYCstudio/p/7211050.html