记录编号	329293	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	4.279 s
提交时间	2016-10-25 07:54:00	内存使用	0.31 MiB

/*
	Name: 矩阵幂之和 
	Copyright: 
	From：http://cogs.pro/cogs/problem/problem.php?pid=2481 
	Author: Go灬Fire 
	Date: 25/10/16 07:53
	Description: 很练代码能力，要写就一鼓作气写完，中间如果一断，就挂了
				思路清晰，半个小时A了
				需要手写乘，记着手写乘后还要再取一边摸，否则还是会W最后一个点 
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define LL long long
using namespace std;
const int maxn=1010;
LL n,m,mod;
LL mul(LL x,LL y,LL z){
	return (x*y-(LL)(x/(long double)z*y+1e-3)*z+z)%z;
}
struct Node{
	LL a[35][35];
	void Mod( Node & a){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				a.a[i][j]%=mod;
	}
	void init(LL x){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				a[i][j]=0;
		for(int i=1;i<=n;i++)a[i][i]=x;
	}
	Node operator * (const Node & b)const{
		Node c;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				c.a[i][j]=0;
				for(int k=1;k<=n;k++){
					c.a[i][j]+=mul(a[i][k],b.a[k][j],mod);
					c.a[i][j]%=mod;
				}
			}
		}
		return c;
	}
	Node operator + (const Node & b)const{
		Node c;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				c.a[i][j]=0;
				c.a[i][j]=a[i][j]+b.a[i][j];
				c.a[i][j]%=mod;
			}
		}
		return c;
	}
};
struct Matrix{
	Node a[3][3];
	void Init(LL x){
		for(int i=1;i<=2;i++)
			for(int j=1;j<=2;j++)
				a[i][j].init(0);
		for(int i=1;i<=2;i++)a[i][i].init(x);
	}
	Matrix operator * (const Matrix & b)const{
		Matrix c;
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				c.a[i][j].init(0);
				for(int k=1;k<=2;k++){
					c.a[i][j]=c.a[i][j]+(a[i][k]*b.a[k][j]);
					c.a[i][j].Mod(c.a[i][j]);
				}
			}
		}
		return c;
	}
}; 
void Init();
Matrix qpow(Matrix a,LL kk,Matrix mul){
	while(kk){
		if(kk&1)a=a*mul;
		mul=mul*mul;kk>>=1;
	}
	return a;
}
int main(){
	freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout);
    Init();
//    for(;;);
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%lld%lld%lld",&n,&m,&mod);
	Matrix a,mul;
	a.Init(0);mul.Init(0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lld",&a.a[1][1].a[i][j]);
			a.a[1][2].a[i][j]=mul.a[1][1].a[i][j]=a.a[1][1].a[i][j];
		}
	}
	mul.a[2][1].init(1);mul.a[2][2].init(1);
	Matrix ans=qpow(a,m-1,mul);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			printf("%lld ",ans.a[1][1].a[i][j]);
		}
		puts("");
	}
}