1386 Cellular Automaton
A cellular automaton is a collection of cells on a grid of specied 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 dened as min(ji ?? jj; n ?? ji ?? jj). 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 input le contains several test cases, each of them consists of two lines, as described below.
The rst line of the input contains four integer numbers n, m, d, and k (1  n  500, 1  m 
1000000, 0  d < n
2 , 1  k  10000000). The second line contains n integer numbers from 0 to m ?? 1
| initial values of the automaton‘s cells.
Output
For each test case, write to the output, on a line by itself, the values of the n;m-automaton‘s cells after
k d-steps.
Universidad de Valladolid OJ: 1386 { Cellular Automaton 2/2
Sample Input
5 3 1 1
1 2 2 1 2
5 3 1 10
1 2 2 1 2
Sample Output
2 2 2 2 1
2 0 0 2 2

题意：
       一个细胞自动机包含n个格子，每个格子的取值为0~m-1.给定距离d，每次操作后每个格子的值将变为到它距离不超过d的所有格子操作之前的值的和除以m的余数。其中i和j和距离为min{|i - j|,n - |i - j|}。给出n，m，d，k，你的任务是计算操作k次之后每个格子的值。

分析：
       将操作t次以后各格子值写成列向量vt，不难发现vt+1的每一维都是vt中各维的线性组合（模加法）。于是设vt+1=A*vt。

       事实上矩阵A是一个循环矩阵，我们只需要表示它的第一行即可。这样做可以简化乘法运算的复杂度。矩阵A将由下列代码进行构造：

for(int i = 0 ;i <= d ; i++) start.v[i] = 1;

for(int i = n -1 ; i > n - 1 - d ; i--)start.v[i] = 1;

 1 #include <stdio.h> 2 #include <string.h> 3 #define ll long long 4 const int maxn = 505; 5 ll n,m,d,k,a[maxn]; 6 struct mat{ // 结构体循环矩阵，原矩阵式方阵 7     ll v[maxn]; 8     mat() {memset(v,0,sizeof(v));} // 构造函数 9     mat operator*(mat c){ // 重载乘法运算符10         mat ans;11         // 只需计算出循环矩阵的第一行即可12         for(int i = 0 ; i < n ; i++)13         for(int j = 0 ; j < n ; j++)14             ans.v[i] = ((ans.v[i] + v[j] * c.v[(i - j + n) % n]) % m + m) % m;15           return ans;16      }17 };18 // 此处不用担心溢出，况且考虑到不好写单位矩阵，就用的方式啦19 mat pow_mod(mat x,ll k){20     mat y; y.v[0] = 1;21     while(k){22         if(k & 1) y = y * x;23         x = x * x;24         k >>= 1;25     }26     return y;27     // 递归写法28     //if(k == 1) return x;29     //mat sb = x * x;30     //mat ans = pow_mod(sb,k >> 1);31     //if(k & 1) ans = ans * x;32     //return ans;33 }34 int main(){35     while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&k)) {36         mat start;37         for(int i = 0 ; i <= d ; i++)38             start.v[i] = 1;39         for(int i = n - 1 ; i > n - 1 - d ; i--)40             start.v[i] = 1;41         start = pow_mod(start,k);42           for(int i = 0 ; i < n ; i++)43               scanf("%lld",&a[i]);44         for(int i = 0 ; i < n ; i++){45             ll ans = 0;46             for(int j = 0 ; j < n ; j++)47                 ans = ((ans + a[j] * start.v[(i - j + n) % n]) % m + m) % m;48             printf("%lld%c",ans,(i == n - 1 ? ‘\n‘ : ‘ ‘));49           }50      }51     return 0;52 }

View Code

UVa1386