POJ 3150 Cellular Automaton 题解

题目大意:给出一个包含\(n(n\le 500)\)个点的环形数字串,每单位时间后每一位上的数字变为与它距离不超过\(d(d\le \frac{n}{2})\)的位上各个数字之和\(mod\ m\),问\(k(k\le 10,000,000)\)单位时间后各个位上的数字变成了什么。

考虑矩阵乘法

很容易写出转移矩阵(下图为\(n=5,d=1\)时的转移矩阵)

\(\begin{matrix}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\end{matrix}\)

设初始矩阵(即\(1\times n\)的一个矩阵,包含一行初始的数)为\(a\),转移矩阵为\(b\),那么答案为\(a\times b^k\)。用矩阵快速幂,复杂度为\(O(n^3\ log\ k)\),过不了。

我们发现,转移矩阵除了第一行,都是由上一行循环右移一位得到的。这样的矩阵称为循环矩阵。有一个很重要的性质:两个循环矩阵相乘依然是循环矩阵。那么我们算矩阵乘法时只需要算出第一行,第\(i+1\)行由第\(i\)行递推得到就行了。

矩阵乘法复杂度降为\(O(n^2)\),总复杂度\(O(n^2\ log\ k)\),可以过了

 

发表评论

电子邮件地址不会被公开。

*