题目简洁明了，给出矩阵，求前k次方和。
不知道这种方法是叫做二分幂还是倍增法，如果有知道的，请告诉我一下。
具体思想是这样的，A^1+A^2+A^3+......A^n=(E+A^(n/2))*(A^1+A^2+.....A^(n/2))，如果n为奇数，那么我们只要加上多余的哪一项就可以满足条件了，于是我们就通过这个公式不断的二分下去，用一个矩阵保存左边的矩阵的值，然后右边始终一直二分就可以了，整个复杂度是log^2的。
不过，我看别人的代码都比我跑得快，所以鄙人觉得应该有更简洁的方法，求指教啊。。。。
召唤代码君：
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 44
using namespace std; int N,m; struct Mat{
int a[][];
Mat(){
for (int i=; i<N; i++)
for (int j=; j<N; j++) a[i][j]=;
}
Mat(int x){
for (int i=; i<N; i++){
for (int j=; j<N; j++) a[i][j]=;
a[i][i]=;
}
}
Mat operator + (Mat M0) const {
Mat M1;
for (int i=; i<N; i++)
for (int j=; j<N; j++) M1.a[i][j]=(a[i][j]+M0.a[i][j])%;
return M1;
}
Mat operator * (Mat M0) const {
Mat M1;
for (int i=; i<N; i++)
for (int j=; j<N; j++)
for (int k=; k<N; k++)
M1.a[i][j]=(M1.a[i][j]+a[i][k]*M0.a[k][j])%;
return M1;
}
void input(){
for (int i=; i<N; i++)
for (int j=; j<N; j++) scanf("%d",&a[i][j]),a[i][j]%=;
}
void output(){
for (int i=; i<N; i++){
printf("%d",a[i][]);
for (int j=; j<N; j++) printf(" %d",a[i][j]);
printf("\n");
}
printf("\n");
}
}; Mat power(Mat M,int P){
Mat tot();
while (P){
if (P&) tot=tot*M;
P>>=,M=M*M;
}
return tot;
} Mat count(Mat M,int P){
Mat M0,E(),M1=E;
while (P){
if (P&) M0=M0+M1*power(M,P);
P>>=;
M1=M1*(E+power(M,P));
}
return M0;
} int main(){
Mat M;
while (scanf("%d%d",&N,&m) && N!=){
M.input();
M=count(M,m);
M.output();
}
return ;
}