题解：P15650 [省选联考 2026] 摩卡串 / string

· · 题解

我是奶龙。

solution

考虑我们要构造一个最短的 01 串 t，满足：

首先我们先考虑如何维护一个子串严格小于 s。

如果 t 的一个子串（不妨设为 t 的某个后缀）的字典序严格小于 s，它必定属于以下两种情况之一：

而一旦出现了第二种情况里的失配，那么无论我们再向这个后缀添加什么字符，他都会永远严格小于 s。我们可以称这种后缀为 X 情况。

现在我们要维护后缀与 s 的匹配情况，不妨考虑 KMP 自动机。

我们在 KMP 自动机上匹配，假设当前状态（最长匹配前缀长度）为 u，此时我们在末尾追加了一个字符 c \in \{0, 1\}，转移到了新状态 u'。

考虑一下对于新形成的（以刚加入的字符结尾的）所有子串，有哪些是严格小于 s 的。

这个东西我们可以通过预处理 KMP 的 fail 树，在转移的时后 O(1) 的时间算出增量：

  1. 新增的 X 情况数量： 只有当新加入的字符 c = 0 时，才有可能产生新的 X 后缀。具体来说，如果在当前状态 u 的 fail 链上，存在某个节点 v 满足 s_{v+1} = 1，那么这个原本匹配了 v 长度的后缀，在遇到 0 后就会永久变小。

    令 f_u 为：当在节点 u 新增加 0 时，产生的 X 后缀数量：

    f_u =[s_{u+1}== 1] + f_{fail_u}

  2. 当前真前缀情况中的后缀数量： 这也就是到达新状态 u' 后，fail 链上有多少个节点的长度 >0 且 <n。

    令 g_{u'} 为：节点 u' 的 fail 链上合法真前缀的数量。

    g_{u'} =[u' < n] + g_{fail_{u'}}

特别的，这里我们要注意一下空串不算。

现在我们要算最短的 t，我们不妨直接 BFS 求。

考虑我们需要记录什么信息：

然后我们逐个加入字符 c 的时候转移即可。

具体来说，转移方程如下（假设加入的字符为 c \in \{0, 1\}，我们在 KMP 自动机上的转移边为 \text{trans}_{u, c}，且设题目要求的目标值为 T）：

u' = \text{trans}_{u, c} \text{flag}' = \text{flag} \lor (u' == n) cnt_X' = cnt_X + (c == 0 ? f_u : 0)

对于新产生的严格小于 s 的子串数量，它等于延续下来的 X 后缀数量，加上刚变成 X 后缀的数量，再加上当前形成的真前缀数量。所以累加的子串总数 k 转移为：

k' = k + cnt_X' + g_{u'}

但是你考虑到 n \le 200，目标 T \le 3000。因为 cnt_X \le k \le T，理论上的极限状态数高达 200 \times 2 \times \frac{3000^2}{2} \approx 1.8 \times 10^9。

看似时间和空间都无法承受，其实仔细观察一下关于 k' 的转移方程：

k' = k + cnt_X' + g_{u'}

我们分析一下状态数：

在 BFS 搜索树的任意一条合法转移路径上，设经过的深度（即当前串长）为 L，cnt_X 的历史序列为 c_1, c_2, \dots, c_L。一旦某个后缀进入 X 情况就永远无法退出，所以序列必然单调不降。同时，由于树高限制，单步新增的 X 后缀数最多为 n，即增量 c_{i+1} - c_i \le n。

我们当前累计的子串总数 k 包含了历史所有 c_i 的贡献，即 k \ge \sum_{i=1}^L c_i。题目要求 k \le T，这等价于单调非降序列 c 的前缀和必须 \le T。

所以我们为了达到某个较大的 cnt_X 值，在增长最快的情况下（也就是每次增量为 n 的时候），到达该状态所需的前缀和最小为 \sum_{i=1}^{cnt_X / n} (i \cdot n) \approx \frac{cnt_X^2}{2n}。 因为必须满足前缀和 \le T，我们有：

\frac{cnt_X^2}{2n} \le T \implies cnt_X \le \sqrt{2nT}

也就是说 cnt_X 上限并不是 T，而是 O(\sqrt{nT}) 级别。

至于空间问题，我们直接压位存一下或者 bitset 就能过了。

代码过了 QOJ 数据，感觉神了。官方数据出了再贴上来。