POJ 3150 Cellular Automaton

83 阅读 0 评论 55 点赞

我是靠谱客的博主大气大雁，最近开发中收集的这篇文章主要介绍POJ 3150 Cellular Automaton，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

A cellular automaton is a collection of cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules that describe the new state of a cell based on the states of neighboring cells. The order of the cellular automaton is the number of cells it contains. Cells of the automaton of order n are numbered from 1 to n.

The order of the cell is the number of different values it may contain. Usually, values of a cell of order m are considered to be integer numbers from 0 to m − 1.

One of the most fundamental properties of a cellular automaton is the type of grid on which it is computed. In this problem we examine the special kind of cellular automaton — circular cellular automaton of order n with cells of order m. We will denote such kind of cellular automaton as n,m-automaton.

A distance between cells i and j in n,m-automaton is defined as min(|i − j|, n − |i − j|). A d-environment of a cell is the set of cells at a distance not greater than d.

On each d-step values of all cells are simultaneously replaced by new values. The new value of cell i after d-step is computed as a sum of values of cells belonging to the d-enviroment of the cell i modulo m.

The following picture shows 1-step of the 5,3-automaton.

The problem is to calculate the state of the n,m-automaton after k d-steps.

Input

The first line of the input file contains four integer numbers n, m, d, and k (1 ≤ n ≤ 500, 1 ≤ m ≤ 1 000 000, 0 ≤ d < ⁿ⁄₂ , 1 ≤ k ≤ 10 000 000). The second line contains n integer numbers from 0 to m − 1 — initial values of the automaton’s cells.

Output

Output the values of the n,m-automaton’s cells after k d-steps.

Sample Input

sample input #1
5 3 1 1
1 2 2 1 2

sample input #2
5 3 1 10
1 2 2 1 2

Sample Output

sample output #1
2 2 2 2 1

sample output #2
2 0 0 2 2

Source

Northeastern Europe 2006

woc，这题太神了，具体参见http://hzwer.com/1817.html

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=505;
int n,d,k;
long long m,num[N],a[N],b[N];
void mul(long long c[],long long d[],long long ans[])
{
	long long t[N];
	memset(t,0,sizeof(t));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
				t[i]=(t[i]+c[j]*d[(i-j+n)%n])%m;
	for(int i=0;i<n;i++)
		ans[i]=t[i];
}
int main()
{
	scanf("%d%lld%d%d",&n,&m,&d,&k);
	for(int i=0;i<n;i++)
		scanf("%lld",&num[i]);
	for(int i=0;i<=d;i++)
		a[i]=1;
	for(int i=n-1;i>=n-d;i--)
		a[i]=1;
	b[0]=1;
	while(k)
	{
		if(k&1)
			mul(b,a,b);
		k>>=1;
		mul(a,a,a);
	}
	mul(num,b,num);
	for(int i=0;i<n;i++)
		printf("%d ",num[i]);
	printf("n");
	return 0;
}