在讲矩阵快速幂之前，先引入整数快速幂的概念。
为了引出矩阵快速幂，以及说明快速幂算法的好处，我们可以先求整数的幂。如果现在要算X^8: 则X*X*X*X*X*X*X*X*X 按照寻常思路，一个一个往上边乘，则乘法运算进行7次。 用(X*X)*(X*X)*(X*X)*(X*X)这种求法，先进行乘法得X^2，然后对X^2再执行三次乘法，这样去计算则乘法运算执行4次。已经比七次少。所以为了快速算整数幂，就会考虑这种结合的思想。现在考虑应该怎么分让计算比较快。接下来计算整数快速幂。 例如：X^19 19的二进制为：1 0 0 1 1 由(X^m)*(X^n)=X^(m+n) 则X^19=(X^16)*(X^2)*(X^1) 那么怎么来求解快速幂呢。请看下列代码：
求解X^N的值
int QuickPow(int x,int N) { int res = x; int ans = 1; while(N) { if(N&1) { ans = ans * res; } res = res*res; N = N>>1; } return ans; }看了一个整数的快速幂，现在我们就正式介绍矩阵快速幂算法。假如现在有一个n*n的方阵A。所谓方阵就是行数和列数相等的矩阵，先给出一个数M，让算矩阵A的M次幂，A^M在此只要求计算并不需要去深究这个矩阵到底是什么含义。详细看下边的代码部分
代码部分
#include<iostream> #include<algorithm> #include<string> #include<math.h> #include<string.h> #include<sstream> #include<queue> #include <stdio.h> using namespace std; #define inf 0x3f3f3f3 #define LL long long #define pii pair<int ,int> const int N = 1e4+5; const int mod = 9973; int n,k; struct Matrix ///结构体，矩阵类型 { int m[15][15]; }ans,res; Matrix Mul(Matrix a,Matrix b) { Matrix tmp;//定义一个临时的矩阵，存放A*B的结果 for(int i=1;i <= n;i++) { for(int j = 1;j <= n;j++) { tmp.m[i][j] = 0; for(int k = 1;k <= n;k++) { tmp.m[i][j] += a.m[i][k]*b.m[k][j]; } tmp.m[i][j] %= mod; } } return tmp; } ///矩阵快速幂，求矩阵res的N次幂 void quickpower(int N) { //整数快速幂默认的ans是1，矩阵的话ans应为单位矩阵 for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(i == j) ans.m[i][j] = 1; else ans.m[i][j] = 0; } } while(N) { if(N&1) ans = Mul(ans,res); res = Mul(res,res); N = N>>1; } } int main() { int t; scanf("%d",&t); while (t--) { scanf("%d %d",&n,&k); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) scanf("%d",&res.m[i][j]); } quickpower(k); int sum = 0; for (int i = 1; i <= n; i++) sum = (ans.m[i][i]+sum)%mod; printf("%d\n",sum); } return 0; }