schtonn

schtonn

0%

矩阵快速幂简述

Posted on Edited on Valine:

引入

想要了解矩阵快速幂，就不得不提到矩阵的概念。矩阵就像一个二维数组，存储了一组数据，如： \[M=\left[ \begin{matrix} 1&2&3\\ 4&5&6\\ 7&8&9\end{matrix} \right]\] 用 \(M_{i,j}\) 表示矩阵第 \(i\) 行第 \(j\) 列的数据，如 \(M_{2,3}=6\)。

矩阵运算

加法

矩阵的加法和实数加法类似，要求运算的两个矩阵大小相等，将对应位置相加即可。

减法

与加法相同，对应位置相减即可。

乘法

矩阵乘法并非对应位置相乘。

若矩阵 \(A\times B=C\) 有意义，那么 \(A\) 的列数要求与 \(B\) 的行数相等。

若 \(A\) 的列数与 \(B\) 的行数等于 \(n\)：

\[C_{i,j}=\sum_{k=1}^{n}A_{i,k}\times B_{k,j}\]

即结果第 \(i\) 行第 \(j\) 列的值为 \(A\) 的第 \(i\) 行与 \(B\) 的第 \(j\) 列的对应项相乘后求和。

一个很直观的理解是，把矩阵 \(A\) 放在结果的左侧， 矩阵 \(B\) 放在结果的上方，将行与列延长，对应相乘后结果（此例中为 \((7\times2)+(8\times5)+(9\times8)\)）写在交点处。 \[ \begin{array}{clr} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \left[ \begin{matrix} 1&\bold{2}&3\\ 4&\bold{5}&6\\ 7&\bold{8}&9\end{matrix} \right]\\ \left[ \begin{matrix} 1&2&3\\ 4&5&6\\ \bold{7}&\bold{8}&\bold{9}\end{matrix} \right]\left[ \begin{matrix} &\downarrow&&\\ &\downarrow&&\\ \rightarrow&126&&\end{matrix} \right] \end{array}\]

注意矩阵乘法满足结合律，但是不一定满足交换律，\(A\times B\) 成立不一定代表 \(B\times A\) 成立。

除法

\(\cdots\) 我不会，长大后再学习（反正就是乘法的逆运算）。

快速幂

快速幂详见另一篇文章。

矩阵快速幂

由于矩阵的幂符合快速幂所需的性质，所以可以使用直观地直接进行矩阵快速幂，方法和普通快速幂一样，但是要注意乘法顺序。ans的初始值要特别注意。如果想让它充当1，则需要设置成相同阶数的单位矩阵 \(I\)。 \[ I=\left[\begin{matrix}1&0&0&\cdots&0\\0&1&0&\cdots&0\\0&0&1&\cdots&0\\\vdots&\vdots&\vdots&\ddots&0\\0&0&0&0&1\end{matrix}\right] \]

递推

使用矩阵快速幂，可以用 \(O(\log n)\) 的时间复杂度完成 \(n\) 次线性齐次递推，如斐波那契数列。矩阵可以通过递推关系推算出来。一般来说，这里的递推关系用一个列向量来记录运算的过程值，然后通过左乘一个系数矩阵，转移到下一个状态，在这里就是转移到数列的下一位。也就是说：

\[\left[\begin{matrix}1&1\\0&1\end{matrix}\right] \times \left[\begin{matrix}F_{n-1}\\F_{n-2}\end{matrix}\right] = \left[\begin{matrix}F_n\\F_{n-1}\end{matrix}\right]\] \[\because F_1=F_2=1\] \[\therefore F_n=\left[\begin{matrix}1&1\\0&1\end{matrix}\right]^n \times \left[\begin{matrix}1\\1\end{matrix}\right]\]

在这里，一次乘法对应着状态前进一步。

推算矩阵

系数矩阵由转移关系得来。以斐波那契数列为例：

\[\because F_n=1F_{n-1}+1F_{n-2}\] \[F_{n-1}=1F_{n-1}+0F_{n-2}\] \[\therefore M=\left[\begin{matrix}1&1\\1&0\end{matrix}\right]\]

如果直接带入矩阵乘法，你会发现这样转移完全合理，甚至惊人地简洁。

代码（斐波那契数列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "bits/stdc++.h"
using namespace std;
const int N=90;
int n;
struct matrix{
    int v[N+2][N+2];
    int x,y;
}t,I,ans;
int pre[N+2];
ostream&operator<<(ostream&ous,matrix a){
    for(int i=0;i<a.x;i++){
        for(int j=0;j<a.y;j++){
            ous<<a.v[i][j]<<' ';
        }
        ous<<endl;
    }
    return ous;
}
matrix operator+(matrix a,matrix b){
    matrix c;
    if(a.x!=b.x||a.y!=b.y)return c;
    int x=a.x,y=a.y;
    c.x=x;
    c.y=y;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            c.v[i][j]=(a.v[i][j]+b.v[i][j]);
        }
    }
    return c;
}
matrix operator*(matrix a,matrix b){
    matrix c;
    if(a.y!=b.x)return c;
    int x=a.x,y=b.y,z=a.y;
    c.x=x;
    c.y=y;
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            c.v[i][j]=0;
            for(int k=0;k<z;k++){
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j]);
            }
        }
    }
    return c;
}
void init(){
    t.x=t.y=2;
    I.x=I.y=2;
    t.v[0][0]=t.v[0][1]=t.v[1][0]=1;
    I.v[0][0]=I.v[1][1]=1;
}
int main(){
    cin>>n;
    init();
    int cnt=n;
    ans=I;
    while(cnt){
        if(cnt&1)ans=ans*t;
        t=t*t;
        cnt>>=1;
    }
    cout<<ans.v[0][0]<<endl;
    return 0;
}