记录编号	479903	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.400 s
提交时间	2017-12-24 15:48:53	内存使用	0.39 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long maxn=100;
long long mod,n;
long long mul(long long x,long long y){return (x*y-(long long)(x/(long double)mod*y+1e-3)*mod+mod)%mod;}//暴long long
struct matrix{
	long long a[maxn][maxn];
	matrix(){memset(a,0,sizeof(a));}//初始化 is important
	matrix operator * (const matrix& b)const{
		matrix c;
		for(long long i=1;i<=n;i++)
			for(long long j=1;j<=n;j++)
				for(long long k=1;k<=n;k++)
					c.a[i][j]=(c.a[i][j]+mul(a[i][k],b.a[k][j])%mod)%mod;
		return c;
	}
	matrix operator + (const matrix& b)const{
		matrix c;
		for(long long i=1;i<=n;i++)
			for(long long j=1;j<=n;j++)
				c.a[i][j]=(a[i][j]%mod+b.a[i][j]%mod)%mod;
		return c;
	}
}final;
void power(matrix a,long long b){
	matrix ans,tmp=a;
	for(long long i=1;i<=n;i++)ans.a[i][i]=1;
	while(b){
		if(b&1)final=final+tmp*ans,ans=ans*a;
		tmp=tmp+tmp*a,a=a*a,b/=2;
	}
}
int main(){
	freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout);
	long long k;
	scanf("%lld%lld%lld",&n,&k,&mod);
	matrix p;
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=n;j++)
			scanf("%lld",&p.a[i][j]),p.a[i][j]%=mod;
	power(p,k);
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=n;j++)printf("%lld ",final.a[i][j]);
		printf("\n");
	}
	return 0;
}