记录编号	170250	评测结果	AAAAAAAAAA
题目名称	[UVa 1386] 细胞自动机	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	4.119 s
提交时间	2015-07-12 18:04:09	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define speedup ios::sync_with_stdio(false)
using namespace std;
int n,m,d,k;
int Mod;

struct Matrix{
	long long e[501];
	Matrix operator * (const Matrix& b)
	{
		Matrix c={0};
		for(int i=0;i<n;++i)
		 for (int j=0;j<n;++j)
		  c.e[i]=(c.e[i]+e[j]*b.e[(i-j+n)%n]%Mod)%Mod;
		return c;
	}
	Matrix operator *= (const Matrix& b){
		*this=*this*b;
	}
}M1,M2;

int main()
{
	freopen("cellularautomaton.in","r",stdin);
	freopen("cellularautomaton.out","w",stdout);
	speedup;
 while (scanf("%d%d%d%d",&n,&m,&d,&k)==4)
 {
	memset(M1.e,0,sizeof(M1.e));
	memset(M2.e,0,sizeof(M2.e));
	Mod=m;
	for (int i=0;i<n;++i)
	 scanf("%lld",&M2.e[i]);
	M1.e[0]=1;
	for (int i=1;i<=d;++i)
	 M1.e[i]=1;
	for (int i=n-1;i>=n-d;--i)
	 M1.e[i]=1;
	while (k>0)
	{
		if (k&1)
		 M2*=M1;
		M1*=M1;
		k>>=1;
	};
	for (int i=0;i<n-1;++i)
	 printf("%lld ",M2.e[i]);
	printf("%lld\n",M2.e[n-1]);
 }
 return 0;
}