[ARC119F] AtCoder Express 3
有简单做法，但是pb大神讲了自动机做法。
这么有趣的自动机不去做?亏大发。
有两个重要的观察。
当你出现长度大于 \(4\) 的连续段时，一定会向后走一次并跳过这一段。
某些时候，当你能用同样的步数走到最后的两个格子，且中一个是 \(\rm A\)，一个是 \(B\) 时，可以看作你处于一个既能是 \(\rm A\) ，又能是 \(\rm B\) 的格子上。
那么根据这两个性质，我们可以设计 \(13\) 中状态，在上面贪心地转移，最后统计即可。
以 \(\rm O\) 表示一个既能是 \(\rm A\) 又能是 \(\rm B\) 的格子，这 \(13\) 种状态分别是：
- \(\rm O\)
- \(\rm OA\)
- \(\rm OB\)
- \(\rm AB \dots B\)
- \(\rm A\) 前面有 \(\rm B\)
- \(\rm AA\) 前面有 \(\rm B\)
- \(\rm AAA\) 前面有 \(\rm B\)
- \(\rm AB\)
剩下情况是 \(\rm B\) 关于 \(\rm A\) 的对称。
之后就是简单的计数dp，不再赘述。