算法：矩阵乘法+快速幂改进

1. 声明矩阵结构体

struct matrix { int m,n;//记录行与列，以后会用到 long long mat[][];//实际矩阵，尽量开小 void clear() { m=n=0; memset(mat,0,sizeof mat); } }

 

2.矩阵乘法

matrix mul(const matrix& a,const matrix& b) { matrix ans; int i,j,k; ans.clear();//初始化置零 for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) ans.mat[i][j]+=a.mat[i][k]*b.mat[k][j];//此处可模 return ans; }

3.快速幂改进

在初始化ans时，由于是矩阵，不能置为1，于是置为单位矩阵.

即在声明ans后插入代码：

ans.clear(); for(int i=1;i<=n;i++) ans.mat[i][i]=1;

注意：b的值如果很大，要开long long。

4.调用

计算矩阵a的k次方幂：

matrix ans=qpow(a,k);

以上.