#创作计划# 矩阵快速幂
2026-02-24 19:47:28
发布于：广东
前言
好久没有发帖子了，今天写个创作计划吧。
各位大佬嘴下留情，不喜轻喷，欢迎提建议！
本文将用通俗易懂的方法讲懂矩阵快速幂
铺垫
（若你已经知道且学会快速幂和矩阵乘法，可以直接跳到正文部分）
一、快速幂
先来复习一下快速幂。
int qpow(int base,int pw)
{
int res=1;
while(pw)
{
if(pw%2==1) res=res*base;
base=base*base;
pw/=2;
}
return res;
}
以上是一个简单的快速幂模板。（如果到这里你没有看懂，请重学快速幂）
二、矩阵
矩阵，相当于 c++ 中的二维数组，是一个整齐排列的“数字表格”，举个例子：
这就是一个矩阵，它是一个 行 列的矩阵。（到这里都应该很好理解吧）
三、矩阵的运算
两个矩阵之间支持多种运算，今天我主要讲解加、减、乘法运算。
1、加减运算
加减运算的前提是两个矩阵的行数和列数都相等（即大小形状完全一致）
然后对应位置的数直接相加减得到结果矩阵，结果矩阵的大小形状与初始两个矩阵相同，例如：
减法同理。
2、数乘运算
一个数乘一个矩阵，结果是一个矩阵，大小形状与原矩阵的相同。
具体运算过程是用这个数分别乘矩阵的每一个数，例如：
3、乘法运算
乘法运算的前提是前一个矩阵的行与后一个矩阵的列相等
假设初始矩阵 A 是一个 的矩阵，初始矩阵 B 是一个 的矩阵。
则结果矩阵 C 是一个 的矩阵，且
有点绕，来看例子你就懂了：
（这里没看懂可以多看几次，自己举个例子）
注意：矩阵乘法不支持交换律！！必须保证前一个矩阵的行与后一个矩阵的列相等！
来看这道题
直接按照上面的公式模拟就可以了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct matrix
{
int r,c;
vector<vector<int>>a;
matrix(int n,int m)
{
r=n,c=m;
a.assign(n,vector<int>(m));
}
vector<int>& operator[](int i){return a[i];}
const vector<int>& operator[](int i) const{return a[i];}
matrix operator*(const matrix &b) const
{
matrix ret(r,b.c);
for(int i=0;i<r;i++)
{
for(int j=0;j<b.c;j++)
{
for(int k=0;k<c;k++) ret[i][j]+=a[i][k]*b[k][j];
}
}
return ret;
}
};
signed main()
{
int n,m,k;
cin>>n>>m>>k;
matrix a(n,m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) cin>>a[i][j];
matrix b(m,k);
for(int i=0;i<m;i++)
for(int j=0;j<k;j++) cin>>b[i][j];
auto C=a*b;
for(int i=0;i<C.r;i++)
{
for(int j=0;j<C.c;j++) cout<<C[i][j]<<" ";
cout<<endl;
}
return 0;
}
上面的matrix结构体部分就是矩阵乘法的模板代码，可以背下来（本人在这类问题中习惯下标从 开始）
到此为止，你已经完成了所有铺垫知识的学习，接下来我们步入正题！
正文
矩阵快速幂是一种技巧，用来优化递推类型（动态规划）的问题。
例题1
一下看到这道题，是不是觉得可以秒掉？这不是初学者就会做的题吗？
但是一看数据范围：
好吧，直接傻掉了， 的递推根本过不去！
所以就要用到今天这个算法：矩阵快速幂
我们先做一个大胆的尝试：
然后
还没看出来？再来一个：
我们发现 行 列的那个矩阵里面的值就是斐波那契数列（即 数组）！！！
总结一个规律，求第 项，不就是用 乘上 ，再取出 行 列的矩阵的第一个数吗？
接下来的问题是不是就来到了如何求 吗？
可以使用快速幂！！！
矩阵快速幂！！！
看模板代码之前，还要引入一个概念：单位矩阵（相当于累乘器初始化的 ）
它的主对角线为 ，其余地方为 。（可以自己举几个例子，发现不管它乘什么矩阵，结果都是原来的矩阵）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
struct matrix
{
int r,c;
vector<vector<int>>a;
matrix(int n,int m)
{
r=n,c=m;
a.assign(n,vector<int>(m));
}
vector<int>& operator[](int i){return a[i];}
const vector<int>& operator[](int i) const{return a[i];}
matrix operator*(const matrix &b) const
{
matrix ret(r,b.c);
for(int i=0;i<r;i++)
{
for(int j=0;j<b.c;j++)
{
for(int k=0;k<c;k++) ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%mod;
}
}
return ret;
}
};
matrix qpow(matrix base,int pw)
{
int nn=base.r;
matrix res(nn,nn);
for(int i=0;i<nn;i++) res[i][i]=1;
while(pw)
{
if(pw%2==1) res=res*base;
base=base*base;
pw/=2;
}
return res;
}
和正常快速幂没什么区别，就是做运算的底数是矩阵而已。
那么我们就可以解决上面那道例题了，主函数部分：
signed main()
{
cin>>n;
matrix a(1,2);
a[0][0]=1,a[0][1]=1;
matrix m(2,2);
m[0][0]=0,m[0][1]=1,m[1][0]=1,m[1][1]=1;
matrix ans=qpow(m,n-1);
ans=a*ans;
cout<<ans[0][0]<<endl;
return 0;
}
复杂度： 为矩阵的行/列数，可忽略。
是不是特别简单？
可能有读者看到这里会问了，如何知道那个放到快速幂中的 矩阵是什么呢？每道题的这个矩阵都一样吗？
别急，通过接下来的这道例题，你会明白如何得到这个 矩阵。
例题2
这道题看起来和刚刚那道题很像，只是多了个系数。
还是按照刚刚的思路，我们一起来推理一下 矩阵。
首先我们要先有一个矩阵（向量），里面存储了我们想要的信息。
这道题我们想知道什么呢？
首先肯定是当前这一项 ， 然后还有什么？
我们需要知道下一项，是不是要知道它前面的两项？所以还要存储一个上一项
这个向量的初始数据是 （ 从 开始）
这样就定义好了，就像定义一个状态。接下来要推理 矩阵。
矩阵一定是一个行数等于列数的矩阵。
因为它要能和这个向量相乘，需要满足行数和列数都等于这个向量的数据个数（在这里为 ）
因此 矩阵长这样：
接下来我们看看如何设定 矩阵使得数据能递推下去，即满足下面这个式子：
不难发现左上角填 ，左下角填 ，右上角填 ，右下角填 ：
这道题基本就做完了。
signed main()
{
cin>>p>>q>>x>>y>>n>>m;
matrix a(1,2);
a[0][0]=x,a[0][1]=y;
matrix m(2,2);
m[0][0]=0,m[0][1]=q;
m[1][0]=1,m[1][1]=p;
matrix ans=qpow(m,n-1);
ans=a*ans;
cout<<ans[0][0]<<endl;
return 0;
}
读者可以尝试自己推导例题一的矩阵。
掌握较熟练后，还可以思考如何求斐波那契前 项和，前 项平方和。
拓展例题
最后来看例题3
这道题看上去非常吓人，有读者可能会考虑高精度，但发现 最大有 ，不可行。
考虑 dp。
设 表示考虑加到第 个数的结果对 取模，不难得到状态转移方程：
其中 表示 是几位数。
考虑矩阵快速幂优化。
在这里直接给出递推式，请读者自行推演：
发现 会变化，考虑做多次矩阵快速幂，每次做同样位数的范围。
细节比较多，具体看代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int mod;
struct matrix
{
int r,c;
vector<vector<int>>a;
matrix(int n,int m)
{
r=n,c=m;
a.assign(n,vector<int>(m));
}
vector<int>& operator[](int i){return a[i];}
const vector<int>& operator[](int i) const{return a[i];}
matrix operator*(const matrix &b) const
{
matrix ret(r,b.c);
for(int i=0;i<r;i++)
{
for(int j=0;j<b.c;j++)
{
for(int k=0;k<c;k++) ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%mod;
}
}
return ret;
}
};
matrix qpow(matrix base,int pw)
{
int nn=base.r;
matrix res(nn,nn);
for(int i=0;i<nn;i++) res[i][i]=1;
while(pw)
{
if(pw%2==1) res=res*base;
base=base*base;
pw/=2;
}
return res;
}
void solve()
{
matrix a(1,3);
a[0][0]=0,a[0][1]=1,a[0][2]=1;
matrix ans(3,3);
for(int i=0;i<3;i++) ans[i][i]=1;
matrix m(3,3);
m[0][0]=1,m[0][1]=0,m[0][2]=0;
m[1][0]=1,m[1][1]=1,m[1][2]=0;
m[2][0]=0,m[2][1]=1,m[2][2]=1;
unsigned long long x=1;
while(true)
{
m[0][0]=m[0][0]*10%mod;
if(n<x*10)
{
ans=ans*qpow(m,n-x+1);
break;
}
ans=ans*qpow(m,x*9);
x*=10;
}
ans=a*ans;
cout<<ans[0][0]<<endl;
}
signed main()
{
cin>>n>>mod;
solve();
return 0;
}
结语
终于肝完了，矩阵快速幂还是挺实用的。
其实它类似于一类构造题，需要自己多多练习和领悟。
本文可能有许多没讲懂或没讲全的内容，深感抱歉，但实在是能力有限欢迎提出修改建议。
有帮助，赞一个