矩阵快速幂：
高效计算矩阵的幂次（如A^n）的一种算法，只适用于计算某一项，而不是全部项。
递推公式
-
如果 n为偶数，则：
A^n=A^(n/2)×A^(n/2) -
如果 nnn 为奇数，则：
A^n=A^(n-1)×A
适用场景：
斐波那契数列：通过矩阵的幂计算斐波那契数列的第N项
线性方程组：适用于递推关系和状态转移矩阵的计算
时间效率：
从O(n)->O(logn);
状态转移方程：
Sn=(fn,fn-1,1)*a[N][N]=Sn+1=(fn+1,fn,1);
例题：
AC代码：
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
int m,n,res;
const int N=3;
//矩阵与向量相乘
void nu(int c[],int a[],int b[][N]){//c[]:是存储计算结果的数组，结果是一个向量//a[]:一个长度为N的数组，表示一个向量//b[][N]:一个N*N的矩阵int temp[N]={0};//是一个临时数组，用于存储矩阵与向量乘法的结果for(int i=0;i<N;i++){for(int j=0;j<N;j++){temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;//b中第j行i列的元素乘以a中第j个元素}}memcpy(c,temp,sizeof temp);
}
//矩阵与矩阵相乘
void nul(int c[][N],int a[][N],int b[][N]){//c[][N]:存储矩阵乘法结果的数组int temp[N][N]={0};for(int i=0;i<N;i++){for(int j=0;j<N;j++){for(int k=0;k<N;k++){temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;//第i行k列乘以k行j列}}}memcpy(c,temp,sizeof temp);
}
int main(){cin>>n>>m;int f[N]={1,1,1};int a[N][N]={{0,1,0},{1,1,1},{0,0,1},};//状态转移方程Sn=(fn,fn-1,1)*a[N][N]=Sn+1=(fn+1,fn,1);//矩阵快速幂n--;//因为矩阵递推从f1开始计算if(n){while(n){if(n&1) nu(f,f,a);//判断n是否为奇数nul(a,a,a);n>>=1;}cout<<f[2]<<endl;}else{cout<<1%m<<endl;}return 0;
}
