记录编号	314394	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	3.345 s
提交时间	2016-10-03 08:20:10	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("matrix_sum.in","r",stdin);freopen("matrix_sum.out","w",stdout); chul();Cu
using namespace std;
typedef long long ll;
const ll maxn=35;
ll n,m,mod;
/*ll mul(ll a,ll b){
	ll cnt=0;
	while(b){
		if(b%2)cnt=(cnt+a)%mod;
		a=2*a%mod;
		b>>=1;
	}
	return cnt;
}*/
ll mul(ll x,ll y){
	ll z=mod;
	return (x*y-(ll)(x/(long double)z*y+1e-3)*z+z)%z;
}
struct op{
	ll a[maxn][maxn];
	void init(ll k){
		if(k==1){
			for(ll i=0;i<n;i++)a[i][i]=1;
		}
		else if(k==0){
			for(ll i=0;i<n;i++){
				for(ll j=0;j<n;j++){
					a[i][j]=0;
				}
			}
		}
	}
	op operator*(const op& b)const{
		op c;
		for(ll i=0;i<n;i++){
			for(ll j=0;j<n;j++){
				c.a[i][j]=0;
				for(ll k=0;k<n;k++){
					c.a[i][j]+=(mul(a[i][k],b.a[k][j]));
					c.a[i][j]%=mod;
				}
			}
		}
		return c;
	}
	op operator+(const op& b)const{
		op c;
		for(ll i=0;i<n;i++){
			for(ll j=0;j<n;j++){
				c.a[i][j]=((a[i][j]+b.a[i][j])%mod);
				c.a[i][j]%=mod;
			}
		}
		return c; 
	}
};
struct po{
	op b[3][3];
	void init(op a,op be,op c){
		b[0][0]=a;
		b[0][1]=b[1][1]=be;
		b[1][0]=c;
	}
	void iniit(){
		for(ll i=0;i<2;i++){
			for(ll j=0;j<n;j++){
				b[i][i].a[j][j]=1;
			}
		}
	}
	po operator*(const po& a)const{
		 po c;
		 for(ll i=0;i<2;i++){
			for(ll j=0;j<2;j++){
				c.b[i][j].init(0);
				for(ll k=0;k<2;k++){
					c.b[i][j]=c.b[i][j]+(b[i][k]*a.b[k][j]);
				}
			}
		}
		return c;
	}
};
po qpow(po c,ll k){
	po ans;
	ans.iniit();
	for(;k;k>>=1,c=c*c){
		if(k&1)ans=ans*c;
	}
	return ans;
}
ll cut(ll a){
	return (((a-1)%mod)+mod)%mod;
}
void chul(){
	scanf("%lld%lld%lld",&n,&m,&mod);
	op a,b,e;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			scanf("%lld",&a.a[i][j]);
		}
	}
	po c;
	b.init(1);
	e.init(0);
	c.init(a,b,e);
	c=qpow(c,m+1);
	for(int i=0;i<n;i++){
		c.b[0][1].a[i][i]=cut(c.b[0][1].a[i][i]);
	}
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			printf("%lld ",c.b[0][1].a[i][j]);
		}
		printf("\n");
	}
}
int main(){
	Begin;
}