题解 AT4379 【[AGC027E] ABBreviate】

小粉兔 · 2020-03-14 04:53:36 · 题解

给定一个只含小写字母 \mathtt{a}, \mathtt{b} 的字符串 s，每次你可以执行以下两种操作：

请你求出执行若干次操作后，能够得到的本质不同的字符串有多少个，答案对 ({10}^9 + 7) 取模。

我们考虑判断一个字符串 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} 时：

最后 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|)，评测链接。