矩阵快速幂入门

maichong · 2026-01-15 12:09:57 · 算法·理论

参考文章

1. 矩阵加速：「学习笔记」矩阵快速幂

2. 图上加速：矩阵类优化 dp——矩阵加速优化

概念

矩阵乘法

设矩阵 C=A \times B，则：

1. 若 A 是一个 n \times p 的矩阵，B 是一个 p \times m 的矩阵，则 C 是一个 n \times m 的矩阵。

如图，这是两个 2 \times 2 的矩阵相乘的过程：

::::success[代码]

node cheng(node x,node y){//矩阵x和矩阵y相乘 
    node re;//re为两矩阵相乘所得到的结果
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)re.a[i][j]=0;//初始化矩阵re 
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)re.a[i][j]=(re.a[i][j]+x.a[i][k]*y.a[k][j]%p)%p;
    return re;
}

::::

矩阵快速幂

为了快速求方阵 A ^ n，我们可以使用快速幂来优化时间复杂度。

例题：【模板】矩阵快速幂

::::success[代码]

//这是一份快速求矩阵a的m次方的代码 
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100+10;
long long n,m,p=1e9+7;
struct node{
    long long a[MAXN][MAXN];
}a,ans;
node cheng(node x,node y){//矩阵相乘 
    node re;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)re.a[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)re.a[i][j]=(re.a[i][j]+x.a[i][k]*y.a[k][j]%p)%p;
    return re;
}
node qpow(node x,long long y){//快速幂 
    if(y==1)return x;
    node tt=qpow(x,y/2);
    node re=cheng(tt,tt);
    if(y%2)re=cheng(re,x);
    return re;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&a.a[i][j]);
    ans=qpow(a,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)printf("%lld ",ans.a[i][j]);
        printf("\n");
    }
    return 0;
}

::::

应用

矩阵加速

我们可以使用矩阵来加速线性递推式的转移。

例题：斐波那契数列

我们发现，由于 n 是在 long long 范围以内，所以 O(n) 的暴力递推肯定不行。

于是，我们考虑用矩阵来加速递推。

设答案矩阵为 A(n) = \begin{bmatrix} f(n) & f(n-1) \end{bmatrix}，则 A(n-1) = \begin{bmatrix} f(n-1) & f(n-2) \end{bmatrix}。

现在，我们需要构造一个转移矩阵 V，使 A(n)=A(n-1) \times V。