UVA Live 3704 Cellular Automaton （循环矩阵+快速幂）

UVA Live 3704 Cellular Automaton （循环矩阵+快速幂）

Description

Input

The input file contains several test cases, each of them consists of two lines, as described below.The first 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 11 2 2 1 25 3 1 101 2 2 1 2

Sample Output

2 2 2 2 12 0 0 2 2

题意

一个细胞自动机包含 ​​n​​​ 个格子，每个格子的取值为 ​​(0,m)​​​ ，给定距离 ​​d​​​ ，每次操作后每个格子的值变为与它的距离不超过 ​​d​​​ 的所有格子在操作前的值之和模 ​​m​​​ ，计算 ​​k​​ 次操作后各格子的值。

思路

我们把经过 ​​k​​​ 次操作后各格子的值看作列向量 Vk ，不难发现 Vk 可以用 Vk−1 通过某种变换求得，而这种变换便是 Vk−1 中相邻 2×d+1 个元素的和模 ​​m​​ 。

于是整个变换可以通过矩阵乘法来描述

设 V0 为初始列向量，当 d=1 时：

A=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢110⋯ 111110⋯ 101110⋯ ⋯ 011000⋯ 011010⋯ 011⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

最终答案：

Vk=AkV0

其中 Ak 可以使用矩阵快速幂来求得，时间复杂度 O(n3logk)

注意这一个矩阵是循环矩阵，而循环矩阵之间的乘积仍然是循环矩阵，于是我们可以只存储矩阵的一行，计算的时候也只计算这一行即可，时间复杂度 O(n2logk)

AC 代码

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。