MapGuessing

作者：冯哲

关键字：模拟 容斥 搜索

题目简述

已知有一个初始值均未知的长度为$n$的$01$图灵机和一个磁头,定义以下$4$种操作:

$1.$将磁头左移一位.

$2.$将磁头右移一位.

$3.$将磁头当前所在位置的值赋为$0$.

$4.$将磁头当前所在位置的值赋为$1$.

现在给出一个长度为$len$的操作序列和某个状态,求有多少初始图灵机状态,满足存在一个磁头的初始位置,使得磁头在移动中始终不移出图灵机,且存在一个中间状态等于给出的状态.

$1 \leq n \leq 36$

$1 \leq len \leq 555$

初步分析

由于$n$的范围比较大,不能直接枚举图灵机的状态,考虑从磁头的初始位置入手。

假设枚举了磁头的初始位置,那么我们就可以通过模拟操作,得到磁头是否会移出图灵机以及被修改的位置,如果被修改的位置对不上,那么这种初始位置一定是不合法,否则 考虑最后一次所有被修改的位置都能对应给出状态的时刻(此时被修改的位置一定最多),所有被修改的位置都可以任意选,而未被修改的位置就要和给出状态一致.

现在已经得出了一个磁头初始位置能够满足的所有初始序列,但是一个初始序列可能会被多个磁头满足,所以需要去重.

去重

设磁头初始位置$i$能自由选择的位置集合为$A_i$,所有$A_i$的可重集为$S$,根据经典的容斥定理,可以得到正确的答案为

$\sum_{S' \subset S} (-1)^{|S'|+1}2^{|P|}$,其中$P$为$S'$中所有$A_i$的交集.

通过搜索可以在$O(2^n)$的复杂度内解决这个问题.

复杂度分析

如果在搜索时,当$P$为空集时就停止搜索,就可以通过此题了,下面来分析算法的正确性。

考虑一个磁头在操作中的移动范围$[L,R](L \leq 0,R \geq 0)$,设移动范围长度为$l$,则可行的磁头位置数量至多为$n-l$,而每个磁头$i$可能的被修改位置为$[L+i,R+i]$,即个数最多为$l$.

由于集合要非空,而可能被修改位置是一段区间,那么每次可以选择的那些集合之间最大的左端点距离差不能超过$l$,也就是说能够使得交集非空的磁头位置之间最大的距离差不超过$l$,那么能够使得交集非空的磁头集合数量不会超过$O(n*2^l)$.

由以上分析可得搜索的最大复杂度为$O(min(2^{n-l},n*2^{l}))$,则时间复杂度约为$O(\sqrt{n2^{n}})$.

时间复杂度$O(\sqrt{n2^{n}})$,空间复杂度$O(n^2)$.