感觉这是一个很聪明的 DP 套 DP 啊。

首先我们考虑有一个确定的序列 $X$，其是否能与序列 $A$ 通过一样的按法按出来的 DP 怎么做？定义两个序列能通过一样的按法为两个序列是否匹配，那么我们用 $f_i$ 表示 $A$ 与 $X$ 的前 $i$ 项是否匹配，转移很简单，我们判断最后 $1/2/4$ 位是否能匹配，与之前的答案相拼即可。

下面考虑设计状态。一个数的匹配状态显然最多只和前面三个数是什么有关，所以我们定义 $F_{i,a,b,c,p_1,p_2,p_3,p_4}$ 表示倒数的三个数分别是 $a,b,c$ 且倒数的四个位置的 $f$ 值分别是 $p_1,p_2,p_3,p_4$ 的方案数。对于 $F_i$ 来说，我们枚举第 $i+1$ 个数是什么，并判断 $[i-2,i+1]$ 或 $[i,i+1]$ 或 $i+1$ 这几个区间能否匹配且前面的那一部分是否匹配来决定新的 $p_4$ 的值。这样转移我们考虑的是每一个新数的值是什么，显然这样计数是不重不漏的。

具体地，转移显然是由 $F_{i,a,b,c,p_1,p_2,p_3,p_4}$ 向 $F_{i+1,b,c,d,p_2,p_3,p_4,p^{\prime}}$ 的。显然有下式： $$ F_{i,a,b,c,p_1,p_2,p_3,p_4}\rightarrow F_{i+1,b,c,d,p_2,p_3,p_4,p^{\prime}} $$ $p^{\prime}=1$ 成立条件如下： $$ p^{\prime} = 1 \iff \begin{aligned} & [i-2,i+1]\text{ is valid } \land p_1=1 & \text{(1)} \\ \lor\ & [i,i+1]\text{ is valid } \land p_3=1 & \text{(2)} \\ \lor\ & d=a_{i+1} \land p_4=1 & \text{(3)} \end{aligned} $$ $[L,R]\text{ is valid}$ 表示区间 $[L,R]$ 是否能与 $A$ 序列相应区间匹配。

这样 DP 的状态时间复杂度为 $O(n)$，但是对于每一个 $i$ 来说，枚举状态有 $9^3\times2^4$ 种，转移时要枚举 $9$ 个数。这样常数太大（比 $n$ 都大了），考虑减少状态数。

其实在 $9^3\times2^4$ 种状态中，有很多状态向后转移的效果是一样的，所以我们可以合并且少枚举一些状态，这样会大大减少转移常数。考虑决定 $p^{\prime}$ 的三个条件： $$ \begin{aligned} & [i-2,i+1]\text{ is valid } \land p_1=1 & \text{(1)} \\ & [i,i+1]\text{ is valid } \land p_3=1 & \text{(2)} \\ & d=a_{i+1} \land p_4=1 & \text{(3)} \end{aligned} $$ 先从 $p$ 的角度考虑。如果 $p_1=0$，此时条件 $(1)$ 肯定不能满足了，那么无论 $a$ 是多少，向后转移的结果都是一样的，所以不用记录 $a$ 了。如果 $p_1=p_2=0$，那么最早为 $1$ 的位置是 $p_3$，这是只有条件 $(2)$ 和 $(3)$ 能被满足，同理 $b$ 也没有记录的必要了。如果 $p_1=p_2=p_3=0$，那么只有条件 $(3)$ 有满足的可能，$c$ 也没有记录的必要了。然后从区间匹配的角度去考虑。如果 $(a,b,c)$ 与任意的 $d$ 都不能匹配，$p_1$ 和 $a$ 就没有记录的必要了。同理，如果 $(b,c)$ 与任意的 $(d,e)$ 都不能匹配，同理 $p_2$ 和 $b$ 也就没有记录的必要了。这样状态最多只有 $150$ 种左右，足够通过此题。

在实现代码时，我们可以用unordered_map存储每一个状态，对于每一个 $i$，枚举 $i+1$ 那一位的值并判断新的 $p_4$ 是否合法来写出新的状态，再对其进行剪枝处理合并状态。注意到 $F_i$ 只会转移到 $F_{i+1}$，所以我们使用滚动数组存储 $F_i$，这样大大减少了使用的空间。