UVA - 1386 Cellular Automaton

115 阅读 0 评论 76 点赞

我是靠谱客的博主甜美奇异果，最近开发中收集的这篇文章主要介绍UVA - 1386 Cellular Automaton，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

n个数组成环，每次取每个数及其左右d个距离内的所有数的求和，再对m取模之后作为新值，问你k次操作后每个数是多少。

当d=1时构造矩阵：

$begin{bmatrix} a_{1}&a_{2} &a_{3} & a_{4} & a_{5} end{bmatrix}begin{bmatrix} 1 &1 & 0 & 0 &1 \ 1 &1 & 1 & 0 &0 \ 0& 1& 1 & 1&0 \ 0& 0 &1 & 1 & 1\ 1& 0 & 0& 1 & 1 end{bmatrix}=begin{bmatrix} {a_{1}}'&{a_{2} }' &{a_{3} }' &{a_{4}}' &{ a_{5}}' end{bmatrix}$ ，

可知 $begin{bmatrix} 1 &1 & 0 & 0 &1 \ 1 &1 & 1 & 0 &0 \ 0& 1& 1 & 1&0 \ 0& 0 &1 & 1 & 1\ 1& 0 & 0& 1 & 1 end{bmatrix}$ 是个循环矩阵，行和列相同,只需第一行或者第一列就可得整个矩阵。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=505;
ll a[N],b[N],tmp[N];
int n,m,d,k;

void multi(ll a[],ll b[]){
	memset(tmp,0,sizeof(tmp));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			tmp[i]+=a[j]*b[(i-j+n)%n];
	for(int i=0;i<n;i++)
		a[i]=tmp[i]%m;
}

int main(){
	while(~scanf("%d%d%d%d",&n,&m,&d,&k)){
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
			
		memset(b,0,sizeof(b));
		b[0]=1;
		for(int i=1;i<=d;i++)
			b[i]=b[n-i]=1;
			
		while(k){
			if(k&1)
				multi(a,b);
			multi(b,b);
			k>>=1;
		}
		
		for(int i=0;i<n;i++)
			printf("%lld%c",a[i],i==n-1?'n':' ');
	}
	return 0;
}