题解：AT_arc108_d [ARC108D] AB

可能写的有点烦琐。想省事的直接看后面的总结吧。

---

我们称在某两个相邻 $\texttt {AA}$ 间添加 $S_{\texttt{AB}}$ 为“$S_\texttt{AA}$ 操作”。其余类似。

首先第一步一定是 $S_{\texttt {AB}}$ 操作。即 $s = \texttt A + S_{\texttt {AB}} +\texttt B$。不妨对 $S_{\texttt {AB}}$ 分类讨论。

到最后你会发现 $S_{\texttt{AB}}$ 是 $\texttt A$ 是 $\texttt B$ 都是类似的。我们以 $S_{\texttt {AB}} = \texttt A$ 为例。

第一步后 $s = \texttt {AAB}$。第二步我们还可以继续进行 $S_{\texttt {AB}}$ 操作，得到 $s = \texttt{AAAB}$。以此类推。也就是我们可以凑出任意的 $s = \texttt{AAA}\dots\texttt{AB}$。

总长度需要是 $n$。不妨枚举上面的过程经过了**最多**几次。即 $s = \underbrace{\texttt{AAA}\dots\texttt A}_k\texttt B$（$k < n$）。

（**最多**的含义是，以后我们不再在最后这个空里进行 $S_{\texttt{AB}}$ 操作。）

那么下一步一定在某两个 $\texttt {AA}$ 之间添加 $S_{\texttt {AA}}$。二级分类讨论。

- $S_{\texttt {AA}} = \texttt A$。那么一定有 $s = \underbrace{\texttt{AAA}\dots\texttt A}_{k+1}\texttt B$。这和最开始的过程执行 $k+1$ 次无异。不讨论。

换言之，最终字符串一定形如 $s = \underbrace{\texttt{AAA}\dots\texttt A}_{n-1}\texttt B$。也就是说答案为 $1$。

- $S_{\texttt{AA}} = \texttt B$。那么进行若干步这样的操作后，整个字符串一定形如 $s = \texttt{AA}\dots\texttt {A}\texttt B\texttt{AA}\dots\texttt {A}\texttt B\texttt{AA}\dots\texttt {AB}$，即一个连续连续 $\texttt A$ 段后一定紧跟恰好 $1$ 个 $\texttt B$。

此时如果再进行 $S_\texttt{AB}$ 操作（别忘了 $S_\texttt {AB}=\texttt A$）得到的字符串的形式和这个是一样的。

所以下一步操作一定是 $S_{\texttt {BA}}$ 操作。

三级分类讨论。

- $S_{\texttt{BA}} = \texttt A$。下一步得到的字符串形式还是 $s = \texttt{AA}\dots\texttt {A}\texttt B\texttt{AA}\dots\texttt {A}\texttt B\texttt{AA}\dots\texttt {AB}$。即每个连续 $\texttt B$ 段的长度必为 $1$。做个 DP 即可。
  - $S_{\texttt{AB}} = \texttt B$。连续若干次 $S_\texttt{AB}$ 操作后 $s$ 将变得没有规律。每个连续 $\texttt B$ 段的长度也不固定了。也就是说，除了开头的 $\texttt A$，结尾的 $\texttt B$ 和倒数第二个 $\texttt A$ 固定不变，中间共有 $2^{n-3}$ 种方案。

---

总结一下。当 $S_{\texttt {AB}} = \texttt A$ 时：

- $S_\texttt{AA}=\texttt A$：答案为 $1$。
- $S_{\texttt{AA}} = \texttt B$：
  - $S_{\texttt{BA}} = \texttt A$：考虑 DP。设 $f(i,0/1)$ 表示考虑前 $i$ 个位置，且最后一个位置是 $\texttt A / \texttt B$，且每个连续 $\texttt B$ 段的长度必为 $1$ 的方案数。转移 $f(i,0) +f(i,1) \to f(i+1,0),f(i,1)\to f(i+1,0)$。
  - $S_{\texttt{AB}} = \texttt B$：答案为 $2^{n-3}$。

$S_{\texttt {AB}} = \texttt B$ 几乎一模一样。请读者自行完成。

---

注意需要特判一下 $n = 2$。

代码：<https://atcoder.jp/contests/arc108/submissions/59509364>

正在渲染内容...