题解 AT4379 【[AGC027E] ABBreviate】

### 题意简述 给定一个只含小写字母 $\mathtt{a}, \mathtt{b}$ 的字符串 $s$，每次你可以执行以下两种操作： 1. 选取 $s$ 中连续的两个字符 $\mathtt{aa}$，把它们删去，替换成一个字符 $\mathtt{b}$。 2. 选取 $s$ 中连续的两个字符 $\mathtt{bb}$，把它们删去，替换成一个字符 $\mathtt{a}$。 请你求出执行若干次操作后，能够得到的本质不同的字符串有多少个，答案对 $({10}^9 + 7)$ 取模。 - $1 \le |s| \le {10}^5$。 ### 题解 我们考虑判断一个字符串 $t$ 能否通过 $s$ 变换得到。 假设可以，则对于 $t$ 的每一个字符，都对应了 $s$ 中的一段连续区间。 也就是，$s$ 的一个子串，经过若干次操作后，变成了单一的一个字符 $\mathtt{a}$ 或 $\mathtt{b}$。 这里有个很有趣的结论：如果我们把 $\mathtt{a}, \mathtt{b}$ 分别看作 $1, 2$，则执行操作是不会改变所有字符之和模 $3$ 的结果的。 也就是说，定义 $p(s)$ 为字符串 $s$ 中所有字符之和模 $3$，则 $s$ 经过若干次操作变成 $t$，$p(s)$ 与 $p(t)$ 是相等的。 那么回到变成字符的问题上来，如何判断 $s$ 能不能变成单一的字符 $\mathtt{a}$ 或 $\mathtt{b}$ 呢？ 显然 $p(s)$ 应该等于 $1$ 或者 $2$，这对应了最终变成的是 $\mathtt{a}$ 或者是 $\mathtt{b}$，显然这是必要条件。 但是这并不是充分条件，考虑 $s = \mathtt{ababa}$，虽然 $p(s) = p(\mathtt{a})$，但是根本没法对 $s$ 进行操作，所以不可行。 如果 $s$ 中存在两个相邻的相同字符呢？事实证明，再加上这个条件就是充分的了。 考虑归纳：当 $|s| \le 2$ 时成立；否则只要对第一个位置进行操作，就能使长度变小 $1$ 且还满足条件。 **也就是说，字符串 $\boldsymbol{s}$ 能变成单个字符 $\boldsymbol{c}$ 当且仅当 $\boldsymbol{p(s) = p(c)}$ 且「$\boldsymbol{|s| = 1}$ 或 $\boldsymbol{s}$ 中存在相邻的相同字符」**。 那么再回到一开始的问题：字符串 $t$ 能否通过 $s$ 变换得到？ 很自然地，有一个贪心匹配的算法： 依次考虑 $t$ 中的每一个字符，选择一个 $s$ 的**最短前缀**变换成这个字符，然后删掉这个前缀继续匹配。 举个例子，当 $t = \mathtt{abba}$ 且 $s = \mathtt{aabbabaabaaabab}$ 时： - $t_1 = \mathtt{{\color{red}{a}}}$，选取 $s$ 的满足条件的最短前缀：$s = \mathtt{{\color{red}{a}}abbabaabaaabab}$。 - $t_2 = \mathtt{{\color{blue}{b}}}$，选取 $s$ 的满足条件的最短前缀：$s = \mathtt{{\color{red}{a}}{\color{blue}{abb}}abaabaaabab}$。 - $t_3 = \mathtt{{\color{purple}{b}}}$，选取 $s$ 的满足条件的最短前缀：$s = \mathtt{{\color{red}{a}}{\color{blue}{abb}}{\color{purple}{abaa}}baaabab}$。 - $t_4 = \mathtt{{\color{green}{a}}}$，选取 $s$ 的满足条件的最短前缀：$s = \mathtt{{\color{red}{a}}{\color{blue}{abb}}{\color{purple}{abaa}}{\color{green}{baa}}abab}$。 最后 $s = \mathtt{{\color{red}{a}}|{\color{blue}{abb}}|{\color{purple}{abaa}}|{\color{green}{baa}}|abab}$，被分成了五段（前 $|t|$ 段加上一个未匹配的后缀）。 **特别地，这个最后一段需要满足 $\boldsymbol{p}$ 值为 $\boldsymbol{0}$**，例如这里 $p(\mathtt{abab}) = 0$（因为需要满足 $p(s) = p(t)$）。 我们可以证明：$s$ 能变成 $t$ 当且仅当能够成功分段，且 $s$ 存在两个相邻的相同字符（或 $t = s$）。 **注意：证明部分可以酌情跳过**！ **注意：证明部分可以酌情跳过**！ 注意这里包含了两个条件，第一个是成功分段，第二个是 $s$ 存在相邻的相同字符。 我们先考虑 $s$ **不存在相邻的相同字符**的情况，显然输出 $1$ 即可（当 $t = s$ 时）。 那么在后续证明中假定 $s$ 存在相邻的相同字符，条件变为：**能够成功分段**。 我们首先证明它的必要性，即任意一个合法的 $t$ 都能够成功分段： - 对于某个 $t$，我们考虑它在 $s$ 中对应的每个段。 - 即 $s = s_1 \, s_2 \, \cdots \, s_{|t|}$，这里每个 $s_i$ 都是一个字符串，且 $s_i$ 变成了 $t$ 的第 $i$ 个字符。 - 假设 $t_i$ 对应的 $s_i$ 是**第一个非最短前缀**（也就是说之前的字符对应的前缀都是最短的）。 - 令此时的最短前缀为 $x$，则 $s_i = x \, y$，其中 $p(y) = 0$。 - 因为 $p(y) = 0$，考虑把 $y$ 并入后一个 $s_{i + 1}$，以保证 $s_i$ 的最短性。 - 如果 $s_{i + 1}$ 不存在，也就是 $i = |t|$，则结论自然成立（$y$ 成为最后一段未匹配后缀）。 - 否则当前的 $s_{i + 1} \gets y \, s_{i + 1}$，此时至少需要保证 $s_{i + 1}$ 是合法的，如果合法就可以继续递归。 - 但是问题在于可能不合法，可以发现此时 $|s_{i + 1}| \ge 2$，那么就是 $s_{i + 1}$ 中**不存在相邻的相同字符**。 - 也就是形如 $y = \mathtt{baba}$，而原先的 $s_{i + 1} = \mathtt{b}$ 的这种形式，新的 $s_{i + 1} = \mathtt{babab}$。 - 那么我们注意到，如果把 $s_{i + 1}$ 拆分为 $\mathtt{b|abab}$ 两段，然后把 $\mathtt{abab}$ 继续并入后面进行讨论。 - 这样就可以保证此时的 $s_{i + 1} = \mathtt{b}$，显然是最短的，然后把问题转移到后面了，递归即可。 - 所以我们证明了：任意一个合法的 $t$ 都能够成功分段。 还需要证明它的充分性，即只要能够成功分段，那就一定是合法的： - 考虑最终分段的情况，假如不存在最后一段未匹配后缀，则自然成立，否则： - 假设 $s = s_1 \, s_2 \, \cdots \, s_{|t|} \, s_{|t| + 1}$，其中 $s_{|t| + 1}$ 是未匹配后缀，我们要想办法把这个后缀塞到前面去。 - 首先直接把 $s_{|t|}$ 与 $s_{|t| + 1}$ 合并，如果可行就合法，不过如果不可行呢？ - 类似地，自然有形如 $s_{|t|} = \mathtt{a}$ 和 $s_{|t| + 1} = \mathtt{baba}$ 这种形式。 - 那么我们令 $s_{|t|} = \mathtt{a}$，然后把 $\mathtt{abab}$ 往前转移。 - 因为有「$s$ 中存在相邻的相同字符」这个条件，这个过程一定会因为合并出了相邻的相同字符而停止。 - 所以我们证明了：任意一个能够成功分段的 $t$ 都是合法的。 **证明部分结束**。 **证明部分结束**。 那么我们先特判 $s$ 是 $\mathtt{ababababa}$ 这种形式，直接输出 $1$，否则考虑做一个这样的 DP： 令 $dp(i)$ 表示考虑了 $s$ **从 $\boldsymbol{i}$ 开始的后缀**，能够成功分段的 $t$ 的数量（注意最后未匹配的后缀的 $p = 0$ 的限制）。 则答案就是 $dp(1)$，转移是比较显然的。 我代码中实现的时候，为了方便，把 $t$ 是空串的情况也计入答案，输出的时候要扣除。 时间复杂度为 $\mathcal O (|s|)$，[评测链接](https://atcoder.jp/contests/agc027/submissions/10807660)。