上次的AGC的B题我想了两个多小时，最后还是完全不会。当时我对着打的表，想了一大堆策略，比如Hashlife+压位+FFT+迭代$O(\log{N})$次消除$2$等等乱搞，然而在$10^6$的数据规模面前都没什么用。真的讨厌这种打表没用的观察结论题。前几天又心血来潮去搜索了一下“CSS是否图灵完全”，出乎意料地得到了肯定的回答：CSS可以用来模拟Rule 110。我才知道存在一个基本元胞自动机是图灵完全的，非常震惊。于是打算实现一个快速模拟基本元胞自动机的算法，不要让那两个多小时白费了。
算法
我心中的计划是hashlife的一维版本+压位+小数据打表加速。上次看过小机房里的美国小朋友跑的生命游戏的源码，大概也是这个思路。然而我并不知道Hashlife算法的具体细节，更别提把它魔改成一维的了。所以我先学习了一遍二维的Hashlife算法，发现这个东西是可以扩展到任意维度的，改成一维当然很简单。
算法内容如下：
- 给定长度为$2^{k}$的序列$a$，记录$F(a)$表示$a$演化$2^{k-2}$次之后的$a’[2^{k-2}\dots 3\times 2^{k-2}-1]$，可以发现这个$F(a)$不会引用到$a$中未定义的元素。
- 为了求出$F(a)$，可以考虑分成两步。先求出演化$2^{k-3}$次之后的$a’[2^{k-3}\dots 7\times 2^{k-3}-1]$，再演化$2^{k-3}$次得到答案。
- 这两步都是可以递归解决的，第一步可以用3个长度为$2^{k-1}$序列的答案拼起来，第二步可以用两个长度为$2^{k-1}$序列的答案拼起来。具体细节可以看下面的python。
- 用一个哈希表记忆化$F$。
可以用python描述一下（用python是因为它最接近伪代码并且很短）：
def solve(a:list)->list:
if len(a)<=4:
return bruteforce(a)
if hash(a) in mp:
return mp[hash(a)]
n1,n2=len(a)>>1,len(a)>>2
x,y,z=solve(a[:n1]),solve(a[n2:n1+n2]),solve(a[n1:])
return mp[hash(a)]:=solve(x+y)+solve(y+z)
实现
在我的C++实现中，递归边界不是4，而是2048。边界如此之大是因为我打表预处理了任何一个24位序列演化8次之后的中间8位（就是四毛子那一类思想）。并且暴力可以压位，在先除掉了一个64的前提之下还是跑的飞快。然而再快的暴力也只是暴力，边界开得更大就会变慢。
为了更加简洁地支持取子串与合并子串的操作，我按照惯例使用了std::basic_string。完全无法想象用std::vector会有多丑陋。
为了代码方便，我只处理了输入长度为$2^k$的序列，将两侧填充为无限多个0，然后输出演化$2^{k-1}$次之后的结果。这个对于我来说完全够用了。
测试
基本元胞自动机一共有256个规则，本质不同的只有88种。Wolfram把这256个自动机分成了4类。
- 第一类：收敛到稳定态
- 第二类：进入循环
- 第三类：对初始条件极度敏感的混沌系统
- 第四类：兼备规律而稳定的行为与复杂的交互方式
第一类和第二类的自动机是相当无聊的，在我的测试中只需要0.3s以内就可以模拟长度为$2^{20}$的序列演化$2^{19}$步。有一个Wiki上面也提到了的例外：73号规则，这个规则的周期可以任意长，并且每个周期内的内容完全是混沌的，所以在我的测试中用时像第4类一样久。
我的程序完全不能处理任何一个第三类自动机，在这个情况下会退化成$O(n^2)$的暴力。这是因为Hashlife算法的原理是把不同时期不同位置的类似pattern统一处理，而一个混沌系统是基本找不到这样的相同子问题的。值得一提的是规则102，这就是那道题$\bmod 2$的情况，也是属于混沌系统，然而据我所知$k$阶差分除了FFT是没有什么办法的。
第四类自动机是最有趣的，许多这一类的规则都被猜想是具有通用计算能力，然而目前只有110号规则被证明了。这是和生命游戏最相似的一类，可以看成是一堆子结构的交互。hashlife算法可以记录下来各种子结构的演化与子结构之间交互的结果，所以具有很强大的加速效果。然而不会像一二类那样直接发现规律报告答案，所以长度为$2^{20}$的序列演化$2^{19}$步需要15秒到30秒左右，哈希表大概需要使用300MB的内存，取决于初始条件。我观察了一下搜索树节点个数与序列长度的关系，大概近似于$O(N\log N)$。
