|
#include <iostream>
using namespace std;

const int maxn=32;
int n,k,m;
struct matrix
  {
int m[maxn][maxn];
};
matrix mat;

matrix operator*(const matrix &a,const matrix &b)
  {
matrix res;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
 {
res.m[i][j]=0;
for(k=1;k<=n;k++)
 {
res.m[i][j]+=a.m[i][k]*b.m[k][j];
res.m[i][j]%=m;
}
}
return res;
}

matrix operator+(const matrix &a,const matrix &b)
  {
matrix res;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
res.m[i][j]=(a.m[i][j]+b.m[i][j])%m;
return res;
}

matrix power(int k)
  {
matrix temp,res;
if(k==1)
return mat;
else
 {
temp=power(k/2);
res=temp*temp;
if(k%2==1)
res=res*mat;
return res;
}
}

matrix solve(int k)
  {
matrix temp,res;
if(k==1)
return mat;
else
 {
res=solve(k/2);
if(k%2==1)
 {
temp=power(k/2+1);
res=temp*res+res+temp;
}
else
 {
res=power(k/2)*res+res;
}
return res;
}
}

void printf(const matrix & m)
  {
int i,j;
for(i=1;i<=n;i++)
 {
for(j=1;j<n;j++)
printf("%d ",m.m[i][j]);
printf("%d\n",m.m[i][j]);
}
}

int main()
  {
scanf("%d%d%d",&n,&k,&m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&mat.m[i][j]);
matrix temp=solve(k);
printf(temp);
return 0;
}

|