OI题库

【题目描述】

细胞自动机是指一群处在一个个有特定排列方式的格子中的细胞，它们随着离散的时间演变，每一次演变中，每个细胞都遵循一系列规则，这些规则描述了细胞的新状态和原先周围细胞状态间的关系。细胞自动机的阶数是它包含的细胞个数。这些细胞被命名为1~n。

细胞的阶数是它可能所处的状态个数。通常一个m阶细胞的合法状态是整数0,1,...,m-1.

细胞自动机的基本属性之一是它的格子分布。在这个问题中，我们考虑一种特殊的细胞自动机——环形细胞自动机，包含环形分布的n个m阶细胞。我们将它记为n,m-自动机。

在n-m自动机中，两个细胞i,j之间的距离被定义为min(|i-j|,n-|i-j|)。一个细胞的d-临域指和这个细胞的距离不大于d的细胞集合。

在每次d-演变中，每个细胞的值都同时被新的值取代。d-演变后第i个细胞的值是原先它的d-临域中细胞的值之和模m。

下图显示了一个5-3自动机的一次1-演变。

现在请你计算一个n,m-自动机在k次d-演变后的状态。

【输入格式】

输入文件包含不超过15组数据。

每组数据有2行：

第1行是4个整数n,m,d,k(1<=n<=500,1<=m<=1000000,0<=d<=n/2,1<=k<=10000000)

第2行是n个整数（在区间[0,m-1]内），描述了细胞自动机的初始状态。

【输出格式】

对每组数据，输出一行n个整数，分别描述n-m自动机在k次d-演变后细胞1,2,...,n的状态。

【样例输入】

5 3 1 1

1 2 2 1 2

5 3 1 10

1 2 2 1 2

【样例输出】

2 2 2 2 1

2 0 0 2 2

【来源】

UVa1386 Cellular Automaton

刘汝佳，《算法竞赛入门经典训练指南》表2-12