cellular automaton_automaton locker_h3c cellular(2)

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

————————————————.

题目大意 :

就是有一个N这么大的环 现在有这样的操作每次选取每个数及其左右d个距离内的所有数的和 对m取模之后作为这个数的新值 问你K次操作后 每个数都是多少

解题思路 :

首先根据题中的 图片 观察了一下 发现这道题用矩阵快速幂能够解决

以题目图片为例 能构造出如下的矩阵

[1 1 0 0 1] 这 [1] = [2]

[1 1 1 0 0] 里 [2] = [2]

[0 1 1 1 0] 是 [2] = [2]

[0 0 1 1 1] 乘 [1] = [2]

[1 0 0 1 1] 号 [2] = [1]

然后写了一发矩阵快速幂

写完了 发现程序根本运行不了

找了N久BUG 最后在Q巨的指导下才知道 因为数组太大500*500 导致爆栈了

然后把 函数改成引用 就能运行了 但是还是不能A掉题

然后又找了N久的BUG 换了下思路 发现越来越乱

最后看了一波题解 才知道(如下)这玩意叫做循环矩阵

[1 1 0 0 1]

[1 1 1 0 0]

[0 1 1 1 0]

[0 0 1 1 1]

[1 0 0 1 1]

它的性质可以看着篇文章 后面的部分 目录里找矩阵快速幂就行了

然后终于优化到了N^2

结果最后的结果 莫名的PE PE PE!!!! PE 了5 发我也是醉了 最醉了的是 到最后我也没明白为什么PE

然后找了一发大神的代码 直接AC了。。。

格式没问题啊，，，

然后就没有然后了 这题 做的太闹心了 在群里问问题的时候还被 菊菊们讽刺了一波。cellular automaton。cellular automaton。

算了 最后附上本题代码

————————-.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shouji/article-51783-2.html