记录编号	434618	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	4.793 s
提交时间	2017-08-08 13:54:32	内存使用	0.88 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int n;
ll K,ki;
inline ll mul(ll x,ll y){return (x*y-(ll)(x/(long double)ki*y+1e-3)*ki+ki)%ki;}
struct matrix
{	ll s[32][32];
	matrix(){mem(s,0);}
	void init(){mem(s,0);for(int i=0;i<n;i++) s[i][i]=1;}
	void cl(){mem(s,0);}
	friend matrix operator * (matrix x,matrix y)
	{	matrix z;ll tmp;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)
				{	tmp=mul(x.s[i][k],y.s[k][j])%ki;
					z.s[i][j]+=tmp;z.s[i][j]%=ki;
				}
		return z;
	}
	friend matrix operator + (matrix x,matrix y)
	{	matrix z;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				z.s[i][j]=(x.s[i][j]+y.s[i][j])%ki;
		return z;
	}
	friend matrix operator - (matrix x,matrix y)
	{	matrix z;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				z.s[i][j]=(x.s[i][j]-y.s[i][j]+ki)%ki;
		return z;
	}
}A,E,O,fans;
struct matrix2
{	matrix s[4][4];
	void cl(){for(int i=0;i<2;i++) for(int j=0;j<2;j++) s[i][j].cl();}
	matrix2(){cl();}
	void init(){for(int i=0;i<2;i++) s[i][i].init();}
	friend matrix2 operator * (matrix2 x,matrix2 y)
	{	matrix2 z;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
				{	matrix tmp=x.s[i][k]*y.s[k][j];
					z.s[i][j]=z.s[i][j]+tmp;
				}
		return z;
	}
}B,ans;
int main()
{   freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout);
	scanf("%d%lld%lld",&n,&K,&ki);
	ll tmp;E.init();ans.init();
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{	scanf("%lld",&tmp);
			A.s[i][j]=tmp;
		}
	B.s[0][0]=A;B.s[0][1]=E;B.s[1][0]=O;B.s[1][1]=E;
	ll edg=K+1;
	for(;edg;edg>>=1,B=B*B)
		if(edg&1) ans=ans*B;
	fans=ans.s[0][1]-E;
	for(int i=0;i<n;i++)
	{	printf("%lld",fans.s[i][0]);
		for(int j=1;j<n;j++)
			printf(" %lld",fans.s[i][j]);
		putchar('\n');
	}
	return 0;
}