求矩阵的快速幂
#include <stdio.h>#include <cstring>#define T 10struct matrix{int m[T][T];}res,origin[T];void calmatrix(matrix ori[],int q[][2],int matrix_count);matrix multiply(matrix x,matrix y,int n);int main(void){int matrix_count;int matrix_n_k[T][2];do{scanf("%d",&matrix_count);if(matrix_count>0){for(int i=0;i<matrix_count;i++){scanf("%d %d",&matrix_n_k[i][0],&matrix_n_k[i][1]);for(int j=0;j<matrix_n_k[i][0];j++)for(int k=0;k<matrix_n_k[i][0];k++)scanf("%d",&origin[i].m[j][k]);}calmatrix(origin,matrix_n_k,matrix_count);}}while(matrix_count!=0);printf("finish\n");return 0;}void calmatrix(matrix ori[],int q[][2],int matrix_count){int a,b;for(int count=0;count<matrix_count;count++){int n=q[count][1];memset(res.m,0,sizeof(res.m));for( a=0;a<q[count][0];a++)res.m[a][a]=1; //将res.m初始化为单位矩阵 //这里用到二进制思想，如A^156,而156(10)=10011100(2) ，也就有A^156=>(A^4)*(A^8)*(A^16)*(A^128) while(n){if(n&1){res=multiply(res,ori[count],q[count][0]);}ori[count]=multiply(ori[count],ori[count],q[count][0]);n>>=1;}for( a=0;a<q[count][0];a++){for( b=0;b<q[count][0];b++)printf("%d ",res.m[a][b]);printf("\n");}}}matrix multiply(matrix x,matrix y,int n){int a,b,c;matrix temp;memset(temp.m,0,sizeof(temp.m));for(a=0;a<n;a++)for( b=0;b<n;b++)for( c=0;c<n;c++)temp.m[a][b]+=x.m[a][c]*y.m[c][b];return temp;}
