矩阵加速运算
zxr_zwgh
·
·
个人记录
前置知识
矩阵乘法
对于 r 行 c 列的矩阵 A 和 c 行 t 列的矩阵 B 的乘法 ， 其结果为一个 r 行 t 列的矩阵 M , 其中
M_{i,j} = \sum_{k = 1}^{c}a_{i,k}\times b_{k,j}
矩阵快速幂
结合上述定义不难发现，矩阵乘法是满足结合律的，也就是说，对于任意矩阵都有 A\times B \times C = A\times (B \times C) ，这使得我们可以对矩阵使用快速幂的思想进行快速运算任意矩阵的高次方，也是矩阵加速运算的基础。
矩阵加速运算
例题 : P1962-斐波那契数列
发现n \leq 2^{63} ， 显然无法正常动态规划。
观察一下朴素动态规划的转移方程：
F_n = F_{n - 1} + F_{n - 2}
这显然是一个齐次方程，对于所有齐次方程，都可以考虑使用矩阵快速幂来进行加速。
考虑定义矩阵
\begin{pmatrix}
F_{n-1} & F_{n-2} \\
\end{pmatrix}
那么我们思考如何将其转移到
\begin{pmatrix}
F_{n} & F_{n-1} \\
\end{pmatrix}
可以发现由状态转移方程，只需要将其乘上
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}
原矩阵就会变成
\begin{pmatrix}
F_{n-1}+F_{n-2} & {F_{n-1}} \\
\end{pmatrix}
即为
\begin{pmatrix}
F_{n} & F_{n-1} \\
\end{pmatrix}
不难发现，我们可以先将F_2 和 F_1 求出构造一个初始矩阵，再将其乘上上述矩阵的 (n-2) 次方就能得到所求矩阵了。
求 n-2 次方的过程可以使用矩阵快速幂来求解。
例题：P7318-人赢
这道题发现递推式变成了a_n = a_{n-1} \times a_{n-2} ，但是传统的矩阵快速幂是无法求解乘法的，考虑如何将其进行转化：
可以尝试写几项：
n , m , nm , nm^2 , n^2m^3 , n^3m^5 ,n^5m^8...
已经不难发现，n 和 m 的系数是一个斐波那契数列，由此就可以使用矩阵快速幂求出第 k 项，需要注意的是，这里斐波那契数列会超出 long\ long 类型的最大值，所以我们要使用拓展欧拉定理来进行处理。
拓展欧拉定理
a^{b \mod\varphi_(p)+\varphi(p)} \equiv a^b\pmod p
所以只需要在矩阵快速幂中给每一项\mod \varphi(10) ，即 4 ，最后再加上即可。
例题：P5175-数列
这道题中递推式是一个齐次方程，但注意到最终求解的是各数平方之和，我们需要考虑将平方之和作为一项写到矩阵里面，不难发现我们还需要将当前数的平方来进行累加操作，那么此处将当前数的平方拆开（来递推）得到：
a_n^2 = x^2a_{n-1}^2+2xya_{n-1}a_{n-2}+y^2a_{n-2}^2
这里发现出现了三项数列中的东西，只需要使用各数的平方和和这三项构造一个矩阵即可，具体的：
可构造
\begin{pmatrix}
S_n & a_{n+1}^2 & a_n^2 & a_{n+1}a_{n} \\
\end{pmatrix}
那么要转移到下一项，就要乘上
\begin{pmatrix}
1 & 0 & 0 & 0 \\
1 & x^2 & 1 & x \\
0 & y^2 & 0 & 0 \\
0 & 2xy & 0 & y \\
\end{pmatrix}
其中S_n = \sum_{i=1}^n a_i^2 , x,y都为给定常数。
正常进行矩阵快速幂即可。