Matrix Power Series
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.
- 输入
- The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10^9) and m (m < 10^4). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.
- 输出
- Output the elements of S modulo m in the same way as A is given.
- 样例输入
-
2 2 4
0 1
1 1 - 样例输出
-
1 2
2 3 - 来源
- POJ Monthly
- 上传者
- 张云聪
#include <iostream>
#include <cstdio> using namespace std; int M=; struct Matrix{
long int line,column;
long int m[][];
};
struct Matr{
long int line,column;
long int m[][];
Matr(Matrix x){
line =x.line*;
column=x.column*;
for(int i=;i<x.line*;i++){
for(int j=;j<x.column;j++){
m[i][j]=x.m[i%x.line][j];
}
}
for(int i=;i<x.line;i++){
for(int j=x.column;j<x.column*;j++){
m[i][j]=;
}
}
for(int i=x.line;i<x.line*;i++){
for(int j=x.column;j<x.column*;j++){
if(i==j){
m[i][j]=;
}else{
m[i][j]=;
}
}
}
}
}; Matr mult(Matr a,Matr b){
Matr ans(a);
ans.line=a.line;
ans.column=b.column;
//ans=inist(ans,0);
for(int i=;i<ans.line;i++){
for(int j=;j<ans.column;j++){
ans.m[i][j]=;
for(int k=;k<ans.column;k++){
ans.m[i][j]+=(a.m[i][k]*b.m[k][j]);
ans.m[i][j]%=M;
}
}
}
return ans;
} Matr fast_matrix(Matr x,int n){
Matr an(x),tmp(x);
for(int i=;i<x.line;i++){
for(int j=;j<x.column;j++){
an.m[i][j]=x.m[i+x.line/][j];
}
}
an.line/=;
while(n){
if(n%!=){
an=mult(an,tmp);
}
tmp=mult(tmp,tmp);
n>>=;
}
return an;
} int main()
{
int n,m,k;
Matrix a;
scanf("%d %d %d",&n,&k,&m);
M=m;
a.line=n;
a.column=n;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
scanf("%d",&a.m[i][j]);
}
}
Matr ans(a);
Matr ans2=fast_matrix(ans,k-);
for(int i=;i<ans2.line;i++){
for(int j=;j<ans2.column/;j++){
printf("%d ",ans2.m[i][j]);
}
printf("\n");
}
return ;
}