Brief description:
…1000：
。给定一个图灵机。。问按照指定的操作序列（长度 m）有多少种初始状态可以到达给定的目标状态。
。。（不论它的初始位置。。。
Live:
255 […预处理生成长度 50 以内的 5^k 模式串。 暴力匹配点位置 DP ] .。。555 [.. 枚举行使用的行数 i，计算出为了得到 s 需要使用的列数 j，累计 pow() * pow() * C() * C() 。。。]。。。1055 [….] 。
…
Analysis:
555
。。 555 最后一步的公式推的不对。。（两处 pow() 应该换成可重组合。。
… 另外如果要使用 O(n) 算法的话，对 i=n/2 （也就是列不产生贡献的情况，要特判。。。
（现场生的话直接用 O(n2) 就不会有事了。。。Mark。。。
1000
。。首先确认使用容斥原理。但是复杂度大概会过高。。之后注意到有一个不自然的条件：
“It is not allowed for the head to leave the tape (i.e., move left from the leftmost cell or right from the rightmost one). Should that happen, the player loses — even if the goal has been reached before the head left the tape.”
。。。猜测使用这个条件进行剪枝。。那么步骤是。
首先扫描一遍操作序列得出求出最大的相对位移。。记做 nn。（后面要用这个量剪枝。。
。。以及合法初始位置的范围 l, r。( n 记做 r – l。。。
考察具体的一个位置 x 。。由于之前已经判断了越界的情况，所以现在只要在中间任意一个过程合法就要纳入统计。。
考察操作对每个位置的影响，有三种情况。。未产生过影响。。修改了这个位置且合法。。修改了这个位置但是不合法。。。
最后者只要出现一个则跳过。。继续进行后续的扫描。。前者初始位置的状态是固定的。。不谈。。中间这种会产生一个2倍的因子。。。。。
。。。直接应用容斥定理 O(2^n*n)。。。之后注意到相隔太远的状态之间不可能产生交集的可以跳过。。（。注意跳过的部分仍然可能有平凡解。！。。（初始状态等于目标状态。。
255.。。（字符串，DP。
。。555.。（组合。。
1055.。（容斥原理 + 剪枝。。
External link:
…
