以下介绍快速幂的原理，实现，应用，推广
?一，快速幂之基本原理和实现
快速幂是用来干什么的？
问题引入：我们初学c语言的时候，肯定会做这样一道题，计算??,其中a,b,p都是正整数
我们很容易想到这样去求
int pow(int a,int b,int p){
int res=1%p;
for(int i=1;i<=b;i++)res=res*a%p;
return res;
}
用底数a乘上结果b次就得到了答案，这么操作的时间复杂度是O(b)的，而当b取的较大的时候（如2e9）我们就不能用这种方法在1s内得到答案了，因为计算机一秒所执行的操作次数约为1e7至1e8次，那么应该怎么办呢？
因此我们引入快速幂这种简单高效的算法
一，初级版本
O(log(b))计算???(其中a,b,p都在?int 范围内)
当然你也可以这么来看，或许会清晰些
实现方式
typedef long long ll ; //define 一下 long long
int qpow(int a,int b,int p){// a,b,p都为int范围内的非负整数
int rt=1%p;
//这里一定要mod p,否则p=1,b=0时会WA hack数据 2 0 1
while(b){//只要b!=0就一直做下去 从b的二进制最低位向最高位扫一遍
if(b&1)rt=(ll)rt*a%p;
// b&1表示把b的二进制最低位取出来，
//如果是1就是奇数，如果0就是偶数
//这里一定要强转成long long后再mod p,否则两个int类型的数相乘会爆int
b>>=1;//b>>=1表示b=b>>1,即b=b/2 ,相当于把二进制下的当前位扔掉，上一位作为当前为
a=(ll)a*a%p;//这里维护的是a的(2^k)次幂
}
return rt;
}
没有注释版本的
typedef long long ll ;
int qpow(int a,int b,int p){
int rt=1%p;
while(b){
if(b&1)rt=(ll)rt*a%p;
b>>=1;a=(ll)a*a%p;
}
return rt;
}
另外一种理解方式（本质和上面的二进制拆分相同）
实现方式
typedef long long ll ; //define 一下 long long
int qpow(int a,int b,int p){// a,b,p都为int范围内的非负整数
if(b==0)return 1%p;//边界条件，b=0直接返回a^0=1
int rt=qpow(a,b/2,p);//算出a^[b/2] ([x]表示x的下取整)
rt=(ll)rt*rt%p;//算出a^([b/2]*2)
if(b&1)rt=(ll)rt*a%p; //如果b是奇数 那么 [b/2]*2=b-1,要再乘一个a
return rt;
}
没有注释版本的
typedef long long ll ;
int qpow(int a,int b,int p){
if(b==0)return 1%p;
int rt=qpow(a,b/2,p);
rt=(ll)rt*rt%p;
if(b&1)rt=(ll)rt*a%p;
return rt;
} 是不是很简单？现在你就可以尝试做这题啦！
洛谷P1226?P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
--------------------------------------------------------------------------------------------------------------------------
二，一些简单的推广
我们从头开始，回顾一下上面讲的内容，我们给出了O(log b)计算???的方法，具体做法是，初始化结果为1，并将b进行二进制拆分，从b的二进制最低位向最高位扫描，每次扫描一个二进制位时，将结果乘上这个二进制位所对结果的贡献，于是就得到了答案。
???
这里的a为整数，运算符为定义在 整数上?的 模p意义下 的乘法，即整数和乘法构成了这样一种运算，我们可以用快速幂这种算法来降低时间复杂度
那么这里的整数能否是其他类型的元素呢？
这里的乘法能否是其它类型的运算符呢？
如果是，那么我们是否也能用快速幂这种做法来降低其时间复杂度呢？
举个例子
case1:
如果这里的元素类型是整数，而运算符是加法，那么某个整数a和加法运算符作用b次，结果为a*b，但是如果我们没有 乘法运算符，只有加法运算符，那么能不能快速求出b个a相加所得到的值呢？
答案是可以的（涂改比较多...）
?这个做法和快速幂的做法完全类似，代码也十分类似（这个算法被称为快速乘）
typedef long long ll;
int qmul(int a,int b,int p){//b个a相加mod p后的值
//注意，这里的b一定要大于0，不然下面的b>>=1会死循环，因为-1/2=-1
int rt=0;
while(b){
if(b&1)rt=((ll)rt+a)%p;
a=((ll)a+a)%p;
b>>=1;
}
return rt;
}case2:
如果这里的元素类型是整数，而运算符是减法，那么我们是不是也可以仿照上面那么做呢？
经过简单的尝试，我们很容易发现是不行的
为什么不行？
设元素为a，运算符为（⊕）
我们希望计算 a⊕a⊕......⊕a
准确的来说是 不断用当前的结果res，将res更新为res⊕a, 更新若干次所得到结果
即：
先将res初始化为一个值
然后将res更新为res⊕a
继续将更新后的res?再次更新为res⊕a
一直更新若干次，得到最终的res
而我们的快速幂是怎么优化计算的
?我们将b个a通过⊕作用后的结果拆分成了若干段来分别计算
这里面就有个问题，拆分成若干段分别计算后 相邻段之间用⊕作用后的结果（即上图中的右式）是否一定和左式相等？
答案是不一定的，这取决于运算符是什么？
比如说
（3-2-1）?3-（2-1）
那么什么情况下是相等的呢？
我们可以肯定的是，当元素关于运算符⊕满足结合律时上式一定成立
所谓结合律是指 (x⊕y)⊕z=x⊕(y+z)
那么我们可以总结出快速幂的适用范围了，适用于具有结合律的运算！
--------------------------------------------------------------------------------------------------------------------------
三，一般case下的快速幂
在讲快速幂的应用之前，我们再来回顾一下快速幂的做法：
这次对于一般的元素类型a,和一般的具有集合律的运算符⊕，我们去计算 运算符⊕ 作用在元素a上 一共b次所得到的结果。
我们的做法是：将结果初始化为1个缺省值，再将b进行二进制拆分，分别计算每一段的 a被⊕作用若干次的结果，并将这些结果 用运算符⊕作用起来，最终得到所求值。
即
?
写成伪代码大概是这个样子
function qpow(a,b){
res= default ;//缺省值，为作用0次所得到的值
while(b){
if(b&1)res=res⊕a;
a=a⊕a;
b>>=1;
}
return res;
}其中比较关键的是这个缺省值到底是什么？
这个缺省值，可以理解为作用0次所得到的值
但是这说了好像又等于没说，我们可以换个角度思考一下这个缺省值到底是干什么用的
实际上，我们用后面计算出的每一段的结果，来不断更新这个缺省值，最终得到答案
例如
1，我们在计算??时，需要将res初始化为1，
我们先用来更新res，即res=res*
再用来更新res，res=res*
,
最终得到答案
2，我们在用快速乘来计算2+2+2时
先将res初始化为0
?先用个2来更新res，即res=res+2
?再用个2来更新res，res=res+（2+2）
最终得到答案
换作一般的运算符⊕和一般的元素，
我们设第一个用来更新res的元素为c
则第一次更新：?res=res⊕c
因为res是第一次被更新，所以他的值为c
因此我们得到 res⊕c=c
再次强调：c是一般的元素，⊕是一般的运算符
那上面这个式子意味着什么，
意味着这个缺省值是? c 这种元素类型和⊕运算符所确定的代数系统下的幺元（单位元）
说成人话就是：使 任何一个元素 c 和他作用 都等于c本身的那个数
这个数就是res缺省值
那么我们上面所有的疑惑就都能解决了
--------------------------------------------------------------------------------------------------------------------------
四，一种特殊的快速幂之矩阵快速幂
在讲矩阵快速幂前，我们先介绍有关矩阵的一些性质：
性质一：矩阵 在 矩阵加法 下的幺元（单位元）为零矩阵
即对任意矩阵A，满足 A+E=E+A=A 的矩阵E 为零矩阵
性质二：n阶矩阵 在 n阶矩阵与n阶矩阵乘法 下的幺元（单位元）为单位矩阵
（即主对角线为1，其余元素全为0的矩阵）
即对任意n阶矩阵A，满足 A×E=E×A=A 的矩阵A 为单位矩阵
性质三：矩阵对加法满足交换律，结合律，
即对任意n行m列矩阵 A，B，C 都有，A+B=B+A，（A+B）+C=A+(B+C)
性质四，矩阵对乘法满足结合律,
即对任意n行m列矩阵A，m行p列矩阵B，p行q列矩阵C 都有 （A×B）×C=A×（B×C）
上述四条性质的证明都比较容易，下面会经常用到以上结论
我们先给出有关于矩阵的一些模板
const int MOD=1e9+7,N=110;
typedef long long ll;
struct Matrix{
int row,col;//行数列数
int a[N][N];//各元素
Matrix(){//空的构造方法，声明矩阵数组时会用到
}
Matrix(int r,int c){//r行c列零矩阵，矩阵在加法意义下的单位元
memset(a,0,sizeof a);
row=r,col=c;
}
Matrix(int r){//r阶单位矩阵，r阶单位矩阵 ，r阶矩阵在乘法下的单位元
memset(a,0,sizeof a);
row=col=r;
for(int i=0;i<r;i++)a[i][i]=1;
}
Matrix operator+(const Matrix &M)const {//重载加号 矩阵的加法
Matrix rt(M.row,M.col);
for(int i=0;i<rt.row;i++){//各元素为两个矩阵中对应元素相加
for(int j=0;j<rt.col;j++)rt.a[i][j]=((ll)a[i][j]+M.a[i][j])%MOD;
}
return rt;
}
Matrix operator*(const Matrix &M)const{//重载乘号 矩阵与矩阵的乘法
//所得到的矩阵中
//第i行j列的元素为
//第一个矩阵的第i行的元素 和 第二个矩阵的第j列元素 对应相乘 再相加 所得到的值
Matrix rt(row,M.col);
for(int i=0;i<rt.row;i++)for(int j=0;j<rt.col;j++)
for(int k=0;k<col;k++)rt.a[i][j]=(rt.a[i][j]+(ll)a[i][k]*M.a[k][j])%MOD;
return rt;
}
};无注释版本
const int MOD=1e9+7,N=110;
typedef long long ll;
struct Matrix{
int row,col;
int a[N][N];
Matrix(){
}
Matrix(int r,int c){
memset(a,0,sizeof a);
row=r,col=c;
}
Matrix(int r){
memset(a,0,sizeof a);
row=col=r;
for(int i=0;i<r;i++)a[i][i]=1;
}
Matrix operator+(const Matrix &M)const{
Matrix rt(M.row,M.col);
for(int i=0;i<rt.row;i++){
for(int j=0;j<rt.col;j++)rt.a[i][j]=((ll)a[i][j]+M.a[i][j])%MOD;
}
return rt;
}
Matrix operator*(const Matrix &M)const{
Matrix rt(row,M.col);
for(int i=0;i<rt.row;i++)for(int j=0;j<rt.col;j++)
for(int k=0;k<col;k++)rt.a[i][j]=(rt.a[i][j]+(ll)a[i][k]*M.a[k][j])%MOD;
return rt;
}
};以下进入正题之矩阵快速幂
所谓矩阵快速幂，即为元素是n阶矩阵，且运算符为矩阵乘法 ，在这个代数系统下的 若干个相同矩阵的乘积
即计算???
由于矩阵对乘法满足结合律，因此我们的快速幂算法在这个代数系统下 一定是正确的
我们考虑如何去实现他
我们放上快速幂的伪代码
function qpow(a,b){
res= default ;//缺省值，为作用0次所得到的值
while(b){
if(b&1)res=res⊕a;
a=a⊕a;
b>>=1;
}
return res;
}我们一点一点来看：
1，res缺省值是什么？
根据上面的分析，应该是 某种类型的元素 和 定义在它上面的某种运算 所构成的代数系统的 幺元（单位元）
在n阶矩阵和n阶矩阵乘法所构成的代数系统中，幺元为 n阶单位矩阵，因此缺省值为 n阶单位矩阵
2，运算符?⊕是什么？
由矩阵快速幂的定义知，运算符为矩阵乘法
因此我们就可以给出矩阵快速幂的模板了
Matrix qpow(Matrix A,int b){
Matrix rt(A.row);//初始化为单位矩阵
while(b){
if(b&1)rt=rt*A;//这里的乘法为重载过后的矩阵乘法
b>>=1;
A=A*A;//也是重载过后的矩阵乘法
}
return rt;
}
无注释版本
Matrix qpow(Matrix A,int b){
Matrix rt(A.row);
while(b){
if(b&1)rt=rt*A;
b>>=1;
A=A*A;
}
return rt;
} 当然你可以把矩阵快速幂写进矩阵类里面，写成矩阵类里面的一个函数
const int MOD=1e9+7,N=110;
typedef long long ll;
struct Matrix{
int row,col;//行数列数
int a[N][N];//各元素
Matrix(){//空的构造方法，声明矩阵数组时会用到
}
Matrix(int r,int c){//r行c列零矩阵，矩阵在加法意义下的单位元
memset(a,0,sizeof a);
row=r,col=c;
}
Matrix(int r){//r阶单位矩阵，r阶单位矩阵 ，r阶矩阵在乘法下的单位元
memset(a,0,sizeof a);
row=col=r;
for(int i=0;i<r;i++)a[i][i]=1;
}
Matrix operator+(const Matrix &M)const {//重载加号 矩阵的加法
Matrix rt(M.row,M.col);
for(int i=0;i<rt.row;i++){//各元素为两个矩阵中对应元素相加
for(int j=0;j<rt.col;j++)rt.a[i][j]=((ll)a[i][j]+M.a[i][j])%MOD;
}
return rt;
}
Matrix operator*(const Matrix &M)const{//重载乘号 矩阵与矩阵的乘法
//所得到的矩阵中
//第i行j列的元素为
//第一个矩阵的第i行的元素 和 第二个矩阵的第j列元素 对应相乘 再相加 所得到的值
Matrix rt(row,M.col);
for(int i=0;i<rt.row;i++)for(int j=0;j<rt.col;j++)
for(int k=0;k<col;k++)rt.a[i][j]=(rt.a[i][j]+(ll)a[i][k]*M.a[k][j])%MOD;
return rt;
}
Matrix qpow(int b){
Matrix A=*this;//由于下面的操作会修改原矩阵，因此要将原矩阵复制过来，复制本身用*this
Matrix rt(A.row);
while(b){
if(b&1)rt=rt*A;
b>>=1;
A=A*A;
}
return rt;
}
};无注释版本
const int MOD=1e9+7,N=110;
typedef long long ll;
struct Matrix{
int row,col;
int a[N][N];
Matrix(){}
Matrix(int r,int c){
memset(a,0,sizeof a);
row=r,col=c;
}
Matrix(int r){
memset(a,0,sizeof a);
row=col=r;
for(int i=0;i<r;i++)a[i][i]=1;
}
Matrix operator+(const Matrix &M)const {
Matrix rt(M.row,M.col);
for(int i=0;i<rt.row;i++){
for(int j=0;j<rt.col;j++)rt.a[i][j]=((ll)a[i][j]+M.a[i][j])%MOD;
}
return rt;
}
Matrix operator*(const Matrix &M)const{
Matrix rt(row,M.col);
for(int i=0;i<rt.row;i++)for(int j=0;j<rt.col;j++)
for(int k=0;k<col;k++)rt.a[i][j]=(rt.a[i][j]+(ll)a[i][k]*M.a[k][j])%MOD;
return rt;
}
Matrix qpow(int b){
Matrix A=*this;
Matrix rt(A.row);
while(b){
if(b&1)rt=rt*A;
b>>=1;
A=A*A;
}
return rt;
}
};学完了这些之后你就可以愉快地去做这道题了
洛谷P3390?P3390 【模板】矩阵快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
--------------------------------------------------------------------------------------------------------------------------
五，矩阵快速幂的应用一?之 计算线性递推数列的第n项
学了矩阵快速幂的实现方式后，我们能用他来干什么呢？
我们能解决如下问题，
给定数列 {}的前k项?
?,
,...,
,
从第k项开始满足
其中?均为给定常数，
给定n，求出第n项
我们如果暴力的去做，
即对k之后的每个n，都根据线性递推式求出?
那么这样做的时间复杂度为?，不能再1s内得到答案
下面我们介绍矩阵快速幂，来将时间复杂度降至?
我们用一个矩阵来维护数列{}和它满足的线性递推式
由于数列的第n项由前面的k项所决定，因此我们需要一个 “大小” 为k的矩阵 来维护这个递推式
一般地，我们可以考虑用一个k阶矩阵来维护上述的递推关系
一旦这个矩阵确定，那么数列的递推关系就能很好地刻画出来
?
我们观察这个式子，式子右边的一般规律为所有的??
相加
我们知道，矩阵的乘法实际上是 用第一个矩阵的行的元素 与 第二个矩阵的列所对应的元素相乘再相加
写出来就是?
这个式子是不是和上面的递推式长得很像？
因此我们上面的矩阵的第一行可以这么填：
这样就满足了递推式
那么如何去填其他列，使式子左右两边相等呢？
事实上我们这么填就能满足等式了
我们发现，我们中间的矩阵只与数列c和整数k有关，与数列a无关，因此，我们可以一直这么迭代下去，直至 等式右边的k行1列矩阵 为
因此我们数列第n项?，与前k项的关系为
?时间复杂度：我们做一次k阶矩阵与k阶矩阵乘法的时间复杂度为??
快速幂的时间复杂度为??,因此整个算法的时间复杂度就是
相比与暴力做法的快了不少（因为往往n远大于k）
?什么？
太抽象了，你不理解？
我们用一个简单的例子来看一下上述做法具体的实现方式。
洛谷P1962?
P1962 斐波那契数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
要求我们求出Fibonacci数列的第n项，其中n在long long范围内
我们可以这样转换
我们把中间的矩阵记为A，由上述递推式可以得出
代入计算即可
代码如下
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7,N=110;
typedef long long ll;
struct Matrix{
int row,col;
int a[N][N];
Matrix(){}
Matrix(int r,int c){
memset(a,0,sizeof a);
row=r,col=c;
}
Matrix(int r){
memset(a,0,sizeof a);
row=col=r;
for(int i=0;i<r;i++)a[i][i]=1;
}
Matrix operator+(const Matrix &M)const {
Matrix rt(M.row,M.col);
for(int i=0;i<rt.row;i++){
for(int j=0;j<rt.col;j++)rt.a[i][j]=((ll)a[i][j]+M.a[i][j])%MOD;
}
return rt;
}
Matrix operator*(const Matrix &M)const{
Matrix rt(row,M.col);
for(int i=0;i<rt.row;i++)for(int j=0;j<rt.col;j++)
for(int k=0;k<col;k++)rt.a[i][j]=(rt.a[i][j]+(ll)a[i][k]*M.a[k][j])%MOD;
return rt;
}
Matrix qpow(ll b){
Matrix A=*this;
Matrix rt(A.row);
while(b){
if(b&1)rt=rt*A;
b>>=1;
A=A*A;
}
return rt;
}
};
int main(){
ll n;
cin>>n;
if(n<=2)puts("1");
else {
Matrix A(2,2);
A.a[0][0]=1,A.a[0][1]=1;
A.a[1][0]=1,A.a[1][1]=0;
Matrix B(2,1);//存放a0和a1
B.a[0][0]=B.a[1][0]=1;
Matrix C=A.qpow(n-2)*B;
cout<<C.a[0][0];
}
}
是不是非常简单？
类似地，你可以很愉快的去做这道题
洛谷P1939?P1939 【模板】矩阵加速（数列） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我们回顾一下上面这个递推式???
观察一下他的特点
特点一：他是线性齐次的，即只会出现一次项
特点二：他是一元的，因为他只针对数列a
而往往 实际应用当中，我们的数列可能不会有这么完美的性质，即只由前面的若干项决定，且齐次
我们看他的推广形式
推广一：如果是多元齐次的数列，即数列a的第n项，由不同数列的前面若干项所共同决定，那么我们应该怎么办？
例如我们的数列a,b满足
那么数列a,b的第n项该如何确定？
我们是否也可以仿照上面一元齐次线性递推数列的处理方式
来处理多元齐次的线性递推数列？
答案是可以的
我们这样来思考：因为我们要同时维护??和前面若干项之间的关系 和??
和前面若干项之间的关系，那么我们可以把?
?和?
?写进同一个矩阵，以便一起维护
以这边的例子来看，我们希望找到一个4行4列矩阵A满足
经过简单的思考，我们可以这么取A
?于是迭代至第一项和第二项就有
?因此我们完美的解决了上面的问题
既然如此，那么对一般的 k元齐次线性递推数列，我们也很容易按照上面的做法，去求出他的第n项。
推广二，如果是非齐次递推数列，我们能否快速地求出第n项？
实际上，我们对于一般形式的递推数列，是很难简单又快速地求出第n项的
但是对能转化成齐次线性递推数列的情况，我们可以仿照上面这么处理
例如 数列a满足?? ?且?
求 数列的第n项?
这其中，比较麻烦的一个点是??,
我们设???,考虑 此数列各项之间的关系。
我们发现?
此时还是非齐次的
我们再引入数列 c
设
则?
此时，数列 c 满足的递推式还是非齐次的，
我们再引入常数列 d
设?
则
因此我们有
于是
且
我们可以把它们写在一个矩阵里
即
再迭代至第一项和第二项就能得到答案?
即
实际上，上面的递推稍微写复杂了一点点，我们还可以这样写
事实上，只要你正确地维护了递推关系，随便怎么写矩阵都是可以的
综上，我们解决了 多元的 能转换成齐次线性递推的 非齐次线性递推数列的 第n项的 矩阵快速幂求法
学完了这一节，你就可以快乐地去做这几道题了
洛谷P2044 随机数生成器?P2044 [NOI2012] 随机数生成器 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
洛谷P1707 刷题比赛?P1707 刷题比赛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
AcWing1303 Fibonacci前n项和?1303. 斐波那契前 n 项和 - AcWing题库
AcWing1304 佳佳的Fibonacci?1304. 佳佳的斐波那契 - AcWing题库
洛谷P5678 河神?P5678 [GZOI2017]河神 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（广义的矩阵快速幂，考察对快速幂算法的理解）
洛谷P3216 数学作业?P3216 [HNOI2011]数学作业 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（分治，细节略多）
--------------------------------------------------------------------------------------------------------------------------
?六，矩阵快速幂的应用二 之 解决图论中恰好经过k条边 问题
为了介绍本章
我们引入一道例题
hdu2157 How many ways?
给定有向图，询问 从a到b 恰好经过t条边的 不同路径总数
?
?AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MOD=1000,N=22;
typedef long long ll;
struct Matrix{
int row,col;
int a[N][N];
Matrix(){}
Matrix(int r,int c){
memset(a,0,sizeof a);
row=r,col=c;
}
Matrix(int r){
memset(a,0,sizeof a);
row=col=r;
for(int i=0;i<r;i++)a[i][i]=1;
}
Matrix operator+(const Matrix &M)const {
Matrix rt(M.row,M.col);
for(int i=0;i<rt.row;i++){
for(int j=0;j<rt.col;j++)rt.a[i][j]=((ll)a[i][j]+M.a[i][j])%MOD;
}
return rt;
}
Matrix operator*(const Matrix &M)const{
Matrix rt(row,M.col);
for(int i=0;i<rt.row;i++)for(int j=0;j<rt.col;j++)
for(int k=0;k<col;k++)rt.a[i][j]=(rt.a[i][j]+(ll)a[i][k]*M.a[k][j])%MOD;
return rt;
}
Matrix qpow(int b){
Matrix A=*this;
Matrix rt(A.row);
while(b){
if(b&1)rt=rt*A;
b>>=1;
A=A*A;
}
return rt;
}
};
int main(){
int n,m;
while(cin>>n>>m){
if(n==0&&m==0)return 0;
Matrix W(n,n);
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
W.a[u][v]=1;
}
Matrix B(n);//初始化dp矩阵为单位矩阵
int t;
cin>>t;
while(t--){
int k,u,v;
cin>>u>>v>>k;
Matrix C=B*W.qpow(k);
cout<<C.a[u][v]<<"\n";
}
}
}这题可以当作是求恰好经过k条边问题的模板
其推广形式有很多，
绝大多数这样的题都可以用矩阵快速幂来做（只要点数不多，且所求信息易用矩阵维护 且满足结合律）
下面放几道练习题
洛谷P2151 HH去散步???????P2151 [SDOI2009]HH去散步 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（不允许走上一步刚走过的边，点边的互换）
洛谷P2886 牛站?
P2886 [USACO07NOV]Cow Relays G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（恰经过k条边最短路，广义（重新定义矩阵运算符）的矩阵快速幂，也可用bellman-ford算法来做）
洛谷P2233公交车路线
P2233 [HNOI2002]公交车路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
洛谷P5789 可乐
P5789 [TJOI2017]可乐（数据加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（如果常数稍大会被卡）
洛谷P2579沼泽鳄鱼
??????P2579 [ZJOI2005]沼泽鳄鱼 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（不同时间有不同的禁止经过的点）
--------------------------------------------------------------------------------------------------------------------------
七，一些比较奇怪的东西 之 十进制快速幂
上面我们所有关于快速幂的计算中，指数b都是在long long 范围内的，那么b如果是一个位数特别多的大整数时（例如100000位），我们如何算出b次方呢？
我们看快速幂伪代码
function qpow(a,b){
res= default ;//缺省值，为作用0次所得到的值
while(b){
if(b&1)res=res⊕a;
a=a⊕a;
b>>=1;
}
return res;
}其中的初始值default和运算符⊕都没有问题
b&1也没有问题，因为我们判断一个十进制数的奇偶性，只需看他最后一位是奇数or偶数
唯一的问题就出现在??上
高精度的b是没法快速右移一位的，即没法快速除以二，
如果我们手写高精度除法，那么除以二 所花费的时间显然 会正比于b的长度?
而我们需要做 log b 次这样的操作，
b的长度也正比于 log b
这么操作的时间复杂度为?
?当 b的长度为??时，上式算法的时间复杂度达到了?
?量级，显然是不可取的
我们考虑如何去优化他？
我们还是采用快速幂这种思想，只需把每一次操作的时间复杂度从??降至?
?即可
我们上面的快速幂，实际上是对b进行了二进制拆分，拆成 若干段b和运算符（*）的运算 再一起运算的结果
即
? ? ?
我们能否将他进行十进制拆分呢？
当然可以的
事实上
???????
我们从十进制b的最低位向最高位扫描，当扫到第k位时，根据??来算出
,并将结果乘上?
即可。
你可以用十进制快速幂来做一下这道模板题
洛谷P1226?P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int getpow(int a,int b,int p){//计算b较小时，a的b次方，直接循环
int rt=1%p;
for(int i=1;i<=b;i++)rt=(ll)rt*a%p;
return rt;
}
int qpow(int a,string b,int p){//string b存放高精度的b b[0]位b的最高位，字符串b的最后一位为b的最低位
int rt=1%p;
int now=b.size()-1;
while(now>=0){
if(b[now]!='0')rt=(ll)rt*getpow(a,b[now]-'0',p)%p;
now--;
a=getpow(a,10,p);//这里维护的是a的(10^k)次幂
}
return rt;
}
int main(){
int a;
string b="";
scanf("%d",&a);
getchar();
while(1){
char c=getchar();
if(c==' ')break;
b=b+c;
}
int p;
scanf("%d",&p);
cout<<a;
cout<<"^"<<b<<" mod "<<p<<"=";
cout<<qpow(a,b,p);
return 0;
}
于是你可以愉快的做这道题了
?洛谷P1397 矩阵游戏?P1397 [NOI2013] 矩阵游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
（分治，高精度，本题有数论做法，也可用矩阵快速幂做，但是略微卡常）