矩阵乘法递推加速
警告,本文KaTex排版较多,请耐心等待页面加载完成再浏览。
如果有不想看的章节,请查看左侧 TOC 跳过。
0x00 什么是矩阵乘法
这是一个 \rm 2\times 3 的矩阵。
\rm A =\begin{bmatrix}a_{1,1}&a_{1,2}&a_{1,3} \cr a_{2,1}&a_{2,2}&a_{2,3}\end{bmatrix}
这是另一个 \rm 3\times 4 的矩阵。
\rm B =
\begin{bmatrix}
b_{1,1}&b_{1,2}&b_{1,3}&b_{1,4} \\
b_{2,1}&b_{2,2}&b_{2,3}&b_{2,4} \\
b_{3,1}&b_{3,2}&b_{3,3}&b_{3,4}
\end{bmatrix}
矩阵乘法的定义是,对于两个矩阵 \rm m \times p 的矩阵 A 和 \rm p \times n 的矩阵 B,令矩阵 C = A\times B,则矩阵 C 中的第 i 行 j 列的元素可以表示为:
C_{ij} = \sum\limits_{k = 1}^{p} a_{ik}\times b_{kj}
最后乘出来的矩阵是一个 \rm m \times n 的矩阵。
用稍微通俗一点的语言说,就是对于矩阵 C 的第 i 行 j 列的元素值就是 A 矩阵第 i 行的元素和 B 矩阵第 j 列元素一一对应相乘的和。
如果你看不明白,那我就以矩阵 C \rm(2 \times 4) 的一个元素(c_{1,2})举个例子。
长公式不想打了啊啊啊
c_{1,2} = \sum\limits_{k = 1}^{p} a_{1,k}\times b_{k,2} = a_{1,1}\times b_{1,2} + a_{1,2}\times b_{2,2} + a_{1,3}\times b_{3,2}
好,现在你知道什么是矩阵乘法了。尝试一下 Hydro H1005.【模板】矩阵乘法。
0x01 矩阵乘法和递推式之间的关系
先来看一道题:洛谷 P1962 斐波那契数列
这个东西不就是暴力循环就能拿分的题吗?
如果你是这么想的,那么就去逝逝罢,\sf\color{#fadb14} 60\space \color{white}\colorbox{#e74c3c}{Unaccpted}。
1\le n<2^{63} 的范围不卡死你才怪。
接下来的思路有点奇妙。
记斐波那契数列第 n 项为 F_n。
我们假定一个矩阵:
\begin{bmatrix}
F_n&F_{n – 1}
\end{bmatrix}
根据斐波那契数列的递推式,F_n = F_{n – 1} + F_{n – 2}。
我们希望有一个矩阵 \rm base,达到如下效果:
\begin{bmatrix}
F_n&F_{n – 1}
\end{bmatrix} =
\begin{bmatrix}
F_{n – 1}&F_{n – 2}
\end{bmatrix}
\times \rm base
此时 \rm base =
\begin{bmatrix}
1&1 \cr
1&0
\end{bmatrix}。
因此,只需要把 \rm base 推出来就可以了。
又由于矩阵乘法有结合律(在此不做证明),故可以将 F_n 表示如下:
\begin{aligned}
\begin{bmatrix}
F_n&F_{n – 1}
\end{bmatrix} &=
\begin{bmatrix}
F_{n – 1}&F_{n – 2}
\end{bmatrix}\times \rm base\cr
&= \begin{bmatrix}
F_{n – 2}&F_{n – 3}
\end{bmatrix}
\times\rm base \times\rm base\cr &=\cdots\cr&=
\begin{bmatrix}
F_1&F_2
\end{bmatrix}
\times \rm base^{n – 1}\cr &=
\begin{bmatrix}
1&1
\end{bmatrix}
\times\rm base^{n – 1}
\end{aligned}
矩阵/递推式练习
做几道练习题感受一下:(递推式转矩阵)
F_n = 3F_{n-1} + 2F_{n-2}
答案
\begin{bmatrix}
F_n&F_{n – 1}
\end{bmatrix} = \begin{bmatrix}
F_{n – 1}&F_{n – 2}
\end{bmatrix}
\times\begin{bmatrix}
3&1 \cr
2&0
\end{bmatrix}
F_n = 15F_{n-1} – 2F_{n-2}
答案
\begin{bmatrix}
F_n&F_{n – 1}
\end{bmatrix} =\begin{bmatrix}
F_{n – 1}&F_{n – 2}
\end{bmatrix} \times
\begin{bmatrix}
15&1 \cr
-2&0
\end{bmatrix}
F_n = 3F_{n-1} + 2F_{n-2} + F_{n-3}
答案
\begin{bmatrix}
F_n&F_{n – 1}&F_{n-2}
\end{bmatrix} = \begin{bmatrix}
F_{n – 1}&F_{n – 2}&F_{n-3}
\end{bmatrix} \times \begin{bmatrix}
3&1&0 \cr
2&0&1 \cr
1&0&0
\end{bmatrix}
F_n = 3F_{n-1} + 2F_{n-2} + F_{n-3}
答案
\begin{bmatrix}
F_n&F_{n – 1}&F_{n-2}
\end{bmatrix} =
\begin{bmatrix}
F_{n – 1}&F_{n – 2}&F_{n-3}
\end{bmatrix} \times \begin{bmatrix}
3&1&0 \cr
2&0&1 \cr
1&0&0
\end{bmatrix}
F_n = 3F_{n-1} + 2F_{n-2} + 114514
答案
\begin{bmatrix}
F_n&F_{n – 1}&114514
\end{bmatrix} = \begin{bmatrix}
F_{n – 1}&F_{n – 2}&114514
\end{bmatrix} \times
\begin{bmatrix}
3&1&0 \cr
2&0&0 \cr
1&0&1
\end{bmatrix}
还可以将多个递推式合成一个矩阵。
F_n = F_{n-1} + F_{n-2}
S_n = S_{n-1} + F_n
答案
S_n = S_{n-1} + F_n = S_{n-1} + F_{n-1} + F_{n-2}
\begin{bmatrix}
F_n&F_{n – 1}&S_n
\end{bmatrix} = \begin{bmatrix}
F_{n – 1}&F_{n – 2}&S_{n-1}
\end{bmatrix} \times
\begin{bmatrix}
3&1&1 \cr
2&0&1 \cr
1&0&1
\end{bmatrix}
0x03 矩阵快速幂
现在我们已经推出了 \begin{bmatrix}
F_n&F_{n – 1}
\end{bmatrix} = \begin{bmatrix}
1&1
\end{bmatrix} \times base^{n – 1}。
这么做的时间复杂度还是 \rm O(n)(甚至更高),因此我们需要特殊手段进行优化。
这时候,我们就可以搬出矩阵快速幂了。矩阵快速幂与整数快速幂思路基本相同,唯一的不同就是将整数换成了矩阵。
建议封装一下矩阵结构体/类,这样写起来方便一点。注意取模。
总体时间复杂度:\rm O(\log n)
0x04 练习题
题目链接 | 名称 |
---|---|
洛谷 P1962 | 斐波那契数列 |
洛谷 P1349 | 广义斐波那契数列 |
洛谷 P5789 | [TJOI2017]可乐(数据加强版) |
洛谷 P1707 | 刷题比赛 |
洛谷 P1397 | [NOI2013] 矩阵游戏 |
洛谷 P2151 | [SDOI2009] HH去散步 |
洛谷 P3216 | [HNOI2011]数学作业 |
洛谷 P4159 | [SCOI2009] 迷路 |
以及模板题。