矩阵快速幂小结
2018-09-18 06:25:26来源:博客园 阅读 ()
update in 9.17
矩阵
并不想扯什么高端线代的内容因为我也不会
定义
由$n \times m$个数$a_{ij}$排成的$n$行$m$列的数表称为$n$行$m$列的矩阵,简称$n \times m$矩阵。
$$
A =
\begin{bmatrix}
a_{11} & a_{12} & \dots a_{1m} \\
a_{21}, & \dots & \dots \\
a_{31}, & \dots & \dots \\
a_{41} & \dots & a_{nm}
\end{bmatrix}
$$
运算
这里只讲加法减法和乘法,其他的例如矩阵求逆等与本文内容出入较大,有兴趣的可以自己学习
加法
注意,只有行列均相同的矩阵才有加法!
运算也比较简单,把对应位置的数相加得到一个新的矩阵,即为答案
例如
$$
\begin{bmatrix} 1 & 1 & 2 \\ 1 & 0 & 1 \end{bmatrix}
+
\begin{bmatrix} 2 & 3 & 3 \\ 3 & 3 & 2 \end{bmatrix}
=
\begin{bmatrix} 3 & 4 & 5 \\ 4 & 3 & 3 \end{bmatrix}
$$
加法满足以下运算律
$A + B = B + A$
$(A + B) + C = A + (B + C)$
减法
与加法同理。
乘法
这才是重点!!
两个矩阵能进行乘法的前提条件是:一个矩阵的行数等于另一个矩阵的列数
形式化的来说,若$A$是$i \times k$的矩阵,那么$B$必须是$k \times j$的矩阵!
他们相乘得到的$C$是$i \times j$的矩阵
其中$C_{ij} = \sum_{i = 1}^n A_{ik} * B_{kj}$
比如
$$
\begin{bmatrix} 1 & 2\\ 2 & 3 \end{bmatrix}
\times
\begin{bmatrix} 2 & 4 & 5 \\ 3 & 4 & 3 \end{bmatrix}
=
\begin{bmatrix} 8 & 12 & 11 \\ 13 & 20 & 19 \end{bmatrix}
$$
乘法满足结合律,左分配律,右分配律,即
$(A \times B) \times C = A \times (B \times C)$
$(A + B) \times C = A \times C + B \times C$
$C(A + B) = C \times A + C \times B$
千万注意!矩阵乘法不满足交换律!(很多情况下交换之后都不能相乘)
矩阵快速幂
因为矩阵有结合律,因此我们可以把整数的快速幂推广的矩阵上面
题目链接
同样是利用二进制倍增的思想,不难得到以下代码
其中的base,代表的是单位矩阵,也就是除了对角线全为$1$,其他位置都为$0$的矩阵,可以证明任意矩阵乘单位矩阵都等于自身
显然矩阵快速幂的复杂度为$O(n^3 log k)$
#include<cstdio> #define LL long long using namespace std; const int mod = 1e9 + 7; int N; LL K; struct Matrix { int m[101][101]; Matrix operator * (const Matrix &rhs) const { Matrix ans = {}; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod; return ans; } }; Matrix fastpow(Matrix a, LL p) { Matrix base; for(int i = 1; i <= N; i++) base.m[i][i] = 1;//构造单位矩阵 while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } int main() { scanf("%d %lld", &N, &K); Matrix a; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) scanf("%d", &a.m[i][j]); a = fastpow(a, K); for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= N; j++) printf("%d ", a.m[i][j]); return 0; }
应用
斐波那契数列第$n$项
矩阵快速幂最常见的应用就是优化递推啦
还是从最常见的斐波那契数列说起吧。
众周所知,斐波那契数列的递推公式为$$f_{n} = f_{n - 1} + f_{n - 2}, f_1 = 1, f_2 = 1$$
一般来说,这种看起来长得很萌简单,只与自身的函数值有关(可能带几个常数)的式子,一般都可以用矩阵快速幂来加速。
当然,如果你想找刺激,可以学一下这玩意儿
矩阵快速幂具体是怎么加速递推的呢?
首先我们把斐波那契数列写成矩阵的形式,因为$f_n$的取值与$f_{n - 1}, f_{n - 2}$这两项有关,因此我们需要同时保留这两项的值,我们不难得到一个$2 \times 1$的矩阵
$$
\begin{bmatrix}
f_{n} \\
f_{n - 1}
\end{bmatrix}
$$
现在我们要进行递推,也就是得到这样一个矩阵
$$
\begin{bmatrix}
f_{n + 1} \\
f_{n}
\end{bmatrix}
$$
展开
$$
\begin{bmatrix}
f_{n} + f_{n - 1} \\
f_{n}
\end{bmatrix}
$$
观察一下,上面的一项需要用到$f_{n}$和$f_{n - 1}$,下面的一项只需要用到$f_n$
同时结合上面的矩阵乘法的定义,我们不难得到一个转移矩阵
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}
\begin{bmatrix} f_{n} \\ f_{n - 1}\\ \end{bmatrix}
=
\begin{bmatrix} f_{n} + f_{n - 1} \\ f_{n}\\ \end{bmatrix}
$$
这样我们乘一次即可递推到下一项。
但是这样好像并没有什么卵用啊,复杂度上还多了个矩阵相乘
嘿嘿
不要忘了,我们前面可以讲过矩阵有结合律的!
这样的话我们只需要把转移矩阵自乘$n - 1$次,然后再与初始矩阵相乘,就能得到答案矩阵啦!
题目链接
// luogu-judger-enable-o2 #include<cstdio> #include<cstring> #define LL long long using namespace std; const int mod = 1e9 + 7; LL K; struct Matrix { int m[101][101], N; Matrix() { memset(m, 0, sizeof(m)); N = 2; } Matrix operator * (const Matrix &rhs) const { Matrix ans; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod; return ans; } }; Matrix fastpow(Matrix a, LL p) { Matrix base; for(int i = 1; i <= base.N; i++) base.m[i][i] = 1;//鏋勯€犲崟浣嶇煩闃? while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } int main() { scanf("%lld", &K); Matrix a; a.m[1][1] = 1; a.m[1][2] = 1; a.m[2][1] = 1; a.m[2][2] = 0; a = fastpow(a, K - 1); printf("%d", a.m[1][1]); return 0; }
路径计数问题
https://www.nowcoder.com/acm/contest/185/B
给出一个 n * n 的邻接矩阵A.A是一个01矩阵 .A[i][j]=1表示i号点和j号点之间有长度为1的边直接相连.求出从 1 号点 到 n 号点长度为k的路径的数目.
做法:直接对给出的矩阵快速幂$k$次,输出$A[1][N]$
解释:考虑矩阵相乘的过程,我们对于要计算的$(i, j)$位置,我们相当于是枚举了一个中间节点$k$,来计算$(i, k) * (k, j)$
其他的常见矩阵推导
$$G_i = a\times G_{i - 1} + b\times G_{i - 2}$$
\begin{equation*}
\begin{bmatrix}
a&b\\
1 & 0\\
\end{bmatrix}^{i - 1}\times
\begin{bmatrix}
G_{1}\\
G_{0}\\
\end{bmatrix}=
\begin{bmatrix}
a&b\\
1 & 0\\
\end{bmatrix}\times
\begin{bmatrix}
G_{i - 1}\\
G_{i - 2}\\
\end{bmatrix}=
\begin{bmatrix}
G_{i}\\
G_{i - 1}\\
\end{bmatrix}
\end{equation*}
$$G_i = a\times G_{i - 1} + i^2$$
\begin{equation*}
\begin{bmatrix}
a&1&0&0\\
0 & 1&2&1\\
0 & 0&1&1\\
0 & 0&0&1\\
\end{bmatrix}^{i}\times
\begin{bmatrix}
G_{0}\\
1\\
1\\
1\\
\end{bmatrix}=
\begin{bmatrix}
a&1&0&0\\
0 & 1&2&1\\
0 & 0&1&1\\
0 & 0&0&1\\
\end{bmatrix}\times
\begin{bmatrix}
G_{i - 1}\\
i^2\\
i\\
1
\end{bmatrix}=
\begin{bmatrix}
G_{i}\\
(i + 1)^2\\
i + 1\\
1
\end{bmatrix}
\end{equation*}
$$G_i = a\times G_{i - 1} + i^3$$
\begin{equation*}
\begin{bmatrix}
a&1&0&0&0\\
0 & 1&3&3&1\\
0 & 0&1&2&1\\
0 & 0&0&1&1\\
0 & 0&0&0&1\\
\end{bmatrix}^{i}*
\begin{bmatrix}
G_{0}\\
1\\
1\\
1\\
1\\
\end{bmatrix}=
\begin{bmatrix}
a&1&0&0&0\\
0 & 1&3&3&1\\
0 & 0&1&2&1\\
0 & 0&0&1&1\\
0 & 0&0&0&1\\
\end{bmatrix}\times
\begin{bmatrix}
G_{i - 1}\\
i^3\\
i^2\\
i\\
1
\end{bmatrix}=
\begin{bmatrix}
G_{i}\\
(i + 1)^3\\
(i + 1)^2\\
i + 1\\
1
\end{bmatrix}
\end{equation*}
$$G_i = a\times G_{i - 1} + b^i$$
\begin{equation*}
\begin{bmatrix}
a&1\\
0 & b\\
\end{bmatrix}^{i}\times
\begin{bmatrix}
G_{0}\\
b\\
\end{bmatrix}=
\begin{bmatrix}
a&1\\
0 & b\\
\end{bmatrix}\times
\begin{bmatrix}
G_{i - 1}\\
b^{i}\\
\end{bmatrix}=
\begin{bmatrix}
G_{i}\\
b^{i+1}\\
\end{bmatrix}
\end{equation*}
参考资料
《深入浅出矩阵快速幂及其简单应用》
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:洛谷P2347 砝码称重
- 稀疏矩阵类 2020-06-09
- 前缀和 2020-05-04
- 重载矩阵加法运算 代码参考 2020-04-29
- 螺旋矩阵问题 2020-04-18
- 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的 2020-04-15
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash