记录编号	314551	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	1.268 s
提交时间	2016-10-03 18:41:15	内存使用	0.30 MiB

#include <cstdio>
#include <cstring>
typedef long long TYPE;
typedef long double LB;
TYPE min(TYPE a,TYPE b){return a<b?a:b;}
TYPE N,K,M;
inline TYPE mul(TYPE x,TYPE y){return (x*y-(TYPE)(x/(LB)M*y+1e-3)*M+M)%M;}
struct Matrix{
	TYPE w[31][31];
	Matrix(bool t){memset(w,0,sizeof(w));if(t)for(TYPE i=0;i<N;++i)w[i][i]=1LL;}
	TYPE* operator [](TYPE i){return w[i];}
};
Matrix operator *(Matrix a,Matrix b){
	Matrix c(0);
	for(TYPE i=0;i<N;++i){
		for(TYPE j=0;j<N;++j){
			for(TYPE k=0;k<N;++k){
				c[i][j]=(c[i][j]+mul(a[i][k],b[k][j]))%M;
			}
		}
	}return c;
}
Matrix operator +(Matrix a,Matrix b){
	Matrix c(0);
	for(TYPE i=0;i<N;++i){
		for(TYPE j=0;j<N;++j){
			c[i][j]=(a[i][j]+b[i][j])%M;
		}
	}return c;
}
Matrix prefexpow(Matrix a,TYPE b){
	Matrix c=a,d(0),e(1);
	while(b){
		if(b&1){d=d+c*e;e=e*a;}
		c=c+c*a;a=a*a;b>>=1;
	}return d;
}
Matrix a(0);
int main(){
	freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout);
	scanf("%lld%lld%lld",&N,&K,&M);
	//printf("%lld\n",M);
	for(TYPE i=0;i<N;++i){
		for(TYPE j=0;j<N;++j){
			scanf("%lld",&a[i][j]);
		}
	}a=prefexpow(a,K);
	for(TYPE i=0;i<N;++i){
		for(TYPE j=0;j<N;++j){
			printf("%lld ",a[i][j]);
		}putchar('\n');
	}
	return 0;
}