给定一个矩阵A 要求A + A^2 + A^3 +…. A^k;
对于到n的等比矩阵求和
如果n是偶数:
如果n是奇数:
#include<stdio.h>
#include<string.h>
#include<algorithm> using namespace std; const int maxn = ;
int mod = ;
int n, k; struct matrix {
int mat[maxn][maxn];
}; matrix mat_add(matrix A, matrix B) {
matrix ans;
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
ans.mat[i][j] = A.mat[i][j] + B.mat[i][j];
ans.mat[i][j] %= mod;
}
}
return ans;
} matrix mat_mul(matrix A, matrix B) {
matrix ans;
memset(ans.mat, , sizeof(ans.mat));
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
for(int k=; k<n; k++) {
ans.mat[i][j] += A.mat[i][k] * B.mat[k][j];
ans.mat[i][j] %= mod;
}
}
}
return ans;
} matrix mat_pow(matrix A, int b) {
matrix ans;
matrix p = A;
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
ans.mat[i][j] = (i == j);
}
}
while(b) {
if(b & )
ans = mat_mul(ans, p);
p = mat_mul(p, p);
b >>= ;
}
return ans;
} matrix work(matrix A, int m) {
if(m == )
return A;
matrix t = work(A, m/);
if(m & ) {
matrix cur = mat_pow(A, m/+);
t = mat_add(t, mat_mul(t, cur));
t = mat_add(t, cur);
} else {
matrix cur = mat_pow(A, m/);
t = mat_add(t, mat_mul(t, cur));
}
return t;
} int main() {
while(scanf("%d%d", &n, &k), n) {
matrix A;
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
int x;
scanf("%d", &x);
A.mat[i][j] = x % ;
}
}
matrix ans = work(A, k);
for(int i=; i<n; i++) {
for(int j=; j<n; j++) {
printf("%d%c", ans.mat[i][j], j==n- ? '\n' : ' ');
}
}
printf("\n");
}
return ;
}