【题解】UVA1386 Cellular Automaton(循环矩阵)

题目

洛谷UVA1386 Cellular Automaton

题解

由于操作数(k)较大,不可能一轮轮统计,所以考虑矩阵快速幂,但矩阵乘法的时间复杂度是,还是会超时。

观察转移矩阵的性质,会发现它很有规律,是循环矩阵。循环矩阵定义及性质:1.行向量的每个元素都是前一个行向量各元素依次右移一个位置得到的结果。 2.若a,b是循环矩阵,则a+b,a*b都是循环矩阵。 结论:循环矩阵可以压缩为一个列向量。

在矩阵乘法的运算中,若两个矩阵都为压缩矩阵,则无法直接进行运算,需要将左乘矩阵边解压边运算。 如何解压?找规律。(找规律往往比逻辑推理更简便)假设a矩阵压缩后为b向量。

a[1][1]=a[2][2]=a[3][3]=……=a[n][n]=b[1]

a[1][n]=a[2][1]=a[3][2]=……=a[n][n-1]=b[2]

a[1][n-1]=a[2][n]=a[3][1]=……=a[n][n-2]=b[3]

……

a[1][2]=a[2][3]=a[3][4]=……=a[n][1]=b[n]

结论:a[i][j]=b[k] , k=(n+1+i-j) mod n 注意加n是为了确保k为正数。注意环形数据中的距离计算技巧。注意:若n+1+i-j=n,取模后k=0,一般数据在环上的问题,下标设为0~n-1比较方便,此处需要特判。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月16日 下午5:07

【小白解析】
此题需要解题人对矩阵有足够深刻的认知,在此仅对各概念作非常浅显的解释。

循环矩阵
此题有一巨大优势:对于圆环的每一个元素,其“够得到”的其他元素(即距离<=d)数量相等。如果列出n阶矩阵,第i行代表元素i的情况,第i行的j列所包含的数值(1或0,参考第31行)代表对于元素i,元素j是否可参与自己的操作。巧妙的是,基于该问题的对称性,这个矩阵可以构成循环矩阵:即第i+1行的内容是第i行整体向右平移一个元素的结果(i行的最后元素到j行第一位)。
以n=3,d=0举例,则转移矩阵NXT为:
1 0 0
0 1 0
0 0 1

压缩矩阵
基于上述条件,不难发现表示一个转移矩阵,仅需要表示它的一行即可,剩余的行均有第一行平移得出。将循环矩阵表示为行向量的操作即为“压缩”。行向量可行,列向量同样可行,此题为方便计算采用后者。
基于上述例子,对应的列向量nxt为:
1
0
0

解压矩阵
当然,有压缩必然需要解压,这样才能进行后续运算。本题目的解压步骤已在原文中详细阐述:

a[i][j]=b[k] , k=(n+1+i-j) mod n

推论过程较为直白,不再赘述。

转移操作
接下来是最关键也最抽象的步骤:如何进行一轮操作?
先考虑只进行一轮操作的情况。首先,储存原始数据的st本身也储存在列向量中。“将元素i更新成[与之距离不超过d的元素(包括自己)的值之和]”,其实就是NXT*st的操作(注意必须st右乘NXT,不可颠倒);NXT中为1的元素,对应了可以参与操作的圆环中的元素,在两矩阵相乘的过程中,扮演“相加”的成分。
例:若初始环为:
1
2
3
则经上述NXT转移后结果为:
(1 0 0) (1) (1)
(0 1 0)*(2)=(2)
(0 0 1) (3) (3)
满足题目要求。读者可以用其他的转移矩阵进行操作,可得到对应的相同结果。

若需要操作两轮,则用操作一轮后得到的结果NXT*st再右乘NXT。以此类推,若需要操作k轮,其结果为:
NXT*NXT*NXT*……(k个NXT)*st=(NXT)^k *st,即为第33行与34行的操作。最终得出的st即为需要的列向量。