矩阵快速幂其实和常数的快速幂相似，复杂度log2(n)
比如说A^10， 10的二进制1010
也就是说A^10 = A^(2^0*0 + 2^1*1 + 2^2*0 + 2^3*1) 注意：荧光标记的字体刚好是利用了1010(2)从右往所数的每一个数字
算A^10的时候不用算10次，而是先算A^2, 然后算(A^2)^2；然后((A^2)^2)^2……这样就少算了很多次，
而A^10 = A^2 * ((A^2)^2)^2
上代码：
#include <cstdio> #include <cstring> #include <iostream> #include <cstdlib> #define N 3 struct matrix { int arr[N][N]; }origin, res; matrix multiply(matrix x, matrix y) { matrix tmp; memset(tmp.arr, 0, sizeof(tmp.arr)); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) tmp.arr[i][j] += x.arr[i][k] * y.arr[k][j]; } } return tmp; } void init() { printf("随机数组如下：\n"); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { origin.arr[i][j] = rand() % 10; res.arr[i][j] = (i == j); printf("%8d", origin.arr[i][j]); } printf("\n"); } printf("\n"); } void cacl(int n) { printf("%d次幂的计算结果如下：\n", n); while(n) { if(n & 1) res = multiply(res, origin); origin = multiply(origin, origin); n >>= 1; } for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) printf("%8d", res.arr[i][j]); printf("\n"); } printf("\n"); } int main() { int n; while(~scanf("%d", &n)) { init(); cacl(n); } return 0; }
原文：http://www.cnblogs.com/rain-1/p/4938453.html