# UVA Live 3704 Cellular Automaton （矩阵快速幂）

## Description

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 diﬀerent 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(|i − j|,n −|i − j|). A denvironment 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.

## 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.

## 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


## 思路

$$$$A =\begin{bmatrix} 1&1&0& \cdots\ &0&1 \\ 1&1&1&0&\cdots\ & 0 \\ 0&1&1&1&0&\cdots\ \\ \cdots\ &0&1&1&1&0 \\ 1&\cdots\ &0&0&1&1 \\ 1&1&\cdots\ &0&0&1 \\ \end{bmatrix}$$$$

## AC 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n,m,d,k;
LL np[500][500];
int idx=0;
struct marx
{
int tot;
marx()
{
tot=idx++;
}
marx mult(const marx&a,const marx&b)
{
marx ans = marx();
for(int i=0; i<n; i++)
{
LL num=0;
for(int j=0; j<n; j++)
{
num=(num+(np[a.tot][(j-i+n)%n]*np[b.tot][j])%m)%m;
}
np[ans.tot][i]=num;
}
return ans;
}
marx mul(const marx&a,const marx&b)
{
marx ans=marx();
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
np[ans.tot][i]=(np[ans.tot][i]+(np[a.tot][j]*np[b.tot][(j-i+n)%n])%m)%m;
return ans;
}
};

marx mult(marx a,LL n)
{
marx ans=marx();
np[ans.tot][0]=1;
while(n)
{
if(n&1)ans=ans.mul(ans,a);
a=a.mul(a,a);
n>>=1;
}
return ans;
}

int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m>>d>>k)
{
memset(np,0,sizeof(np));
idx=0;
marx ans = marx();
for(int i=0; i<n; i++)
cin>>np[ans.tot][i];
marx ap = marx();
for(int j=-d; j<=+d; j++)
np[ap.tot][(j+n)%n]=1;
ans=ans.mult(mult(ap,k),ans);
for(int i=0; i<n; i++)
cout<<np[ans.tot][i]<<((i!=n-1)?" ":"\n");
}

return 0;
}