(前言：这是一道关于矩阵快速幂的问题，介绍矩阵快速幂之前，首先看“快速幂”问题。 在前面的博客里有记录到快速幂取模算法，不过总体的思想总是和取模运算混淆在一起，而忽略了“快速幂”运算本身。计算ab本来就是一个可以加速的过程，“快速幂取模”运算只不过是“快速幂”算法的一个应用罢了。)
一、快速幂运算
这次我们关注快速幂本身：
我们知道离散化处理信息是计算机的热点，把连续数据存储为二进制离散数据是计算机的硬件要求。那么快速幂运算能否也运用这一思想呢，答案是肯定的。
容易发现：A19 = （A16）*（A2）*（A1），而我们在计算A16的过程中可以通过A8*A8来得到，而A8同样可以通过A4*A4来得到，这样以来本来需要16次乘法运算得到的只需要log(16)=4次即可。
A*A = A2
A2*A2 = A4
A4*A4 = A8
A8*A8 =A16
再举例计算A148.我们知道14810=100101002,也就有A148=A128*A16*A4. 观察二进制形式的因子，容易发现这样的规律早就在二进制表示中显露出来了：100101002=100000002+000100002+000001002 =128+16+4。
核心代码表示为： (第3行代码每进行一次，二进制数就少了最后面的一个1。二进制数有多少个1就第3行代码就执行多少次。)
//在一路的A^x次方(x=1,2,4,8,16,...)的结果中，res通过“n的二进制位的值”来选取组成自己的“元素”
while(n){
)
res=res*A;
n>>=;
A=A*A;
}
测试：
#include <iostream>
using namespace std;
//快速计算 A^n
int main(){
int A,n;
;
cin>>A>>n;
//在一路的A^x次方(x=1,2,4,8,16,...)的结果中，res通过“n的二进制位的值”来选取组成自己的“元素”
while(n){
)
res=res*A;
n>>=;
A=A*A;
}
cout<<res;
}
有输入的A^n
二、快速幂取模 ab%c
现在对于ab我们已经拿到尚方宝剑了，我们知道指数运算往往是很容易突破数据储存长度的（long long int 也才64位），所以一些方案处理中要求的只是ab%c而已。（反正这类问题客观存在，你就当我为它的存在杜撰了一个理由吧）
这时候可以运用取模运算的性质：(a*a)%c = (a%c)(a%c)%c
那这样取模运算就可以“镶嵌”在快速幂运算中了： （if语句中“b%2==1”和上面的“n&1”的写法是一样的）
;
a%=c;
){
==){
num=(num*a)%c;
}
b>>; //这一步将b->log2(b)
a=(a*a)%c;
}
三、矩阵快速幂
矩阵快速幂的思想就是跟数的快速幂一样，不过是把“数”换成“矩阵”罢了，在之前的数的乘法运算是用“*”直接运算，而这里需要单独写一个两矩阵相乘的函数以供调用。
这里展示一个示例程序：
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
int N;
struct matrix{
][];
}origin,res;
matrix multiply(matrix x,matrix y){
matrix temp;
memset(temp.a,,sizeof(temp.a));
;i<;i++) {
;j<;j++) {
;k<;k++) {
temp.a[i][j]+=x.a[i][k]*y.a[k][j];
}
}
}
return temp;
}
void init(){
printf("随机数组如下:\n");
;i<;i++){
;j<;j++){
origin.a[i][j]=rand()%;
printf("%8d",origin.a[i][j]);
}
printf("\n");
}
printf("\n");
memset(res.a,,sizeof(res.a));
res.a[][]=res.a[][]=res.a[][]=; //将res.a初始化为单位矩阵
}
void calc(int n){
printf("%d次幂结果如下：\n",n);
while(n) {
)
res=multiply(res,origin);
n>>=;
origin=multiply(origin,origin);
}
;i<;i++) {
;j<;j++)
printf("%8d",res.a[i][j]);
printf("\n");
}
printf("\n");
}
int main(){
while(cin>>N) {
init();
calc(N);
}
;
}
矩阵 快速幂 演示
四、矩阵快速幂的应用
矩阵题目的难点在于构造矩阵，一般用于有能够推出递推式的题目，推出递推式之后，发现递推O(n)的时间复杂度比较大，那么我们可以构造一个矩阵，然后用矩阵快速幂降低到log(n)的时间复杂度
在NYOJ 299中
Fk = A + A2 + A3 + … + Ak
F(k-1) = A + A2 + A3 + … + Ak-1
故 Fk = A + A*F(k-1)
那么可以构造矩阵：
(Fk ，1 ) = (Fk-1 ，1) * (A，0; A，1) = (F1 , 1) * (A，0;A，1)K-1
这样就可以运用矩阵快速幂了。
参考：
2. http://www.cnblogs.com/yan-boy/archive/2012/11/29/2795294.html
3. http://blog.csdn.net/chenguolinblog/article/details/10309423
4. http://blog.csdn.net/y990041769/article/details/39694583
5. http://blog.csdn.net/y990041769/article/details/39716951
6. http://www.matrix67.com/blog/archives/276