不能说的秘密 题解

VinstaG173 · 2025-07-17 23:05:47 · 题解

前言 题外话

这题本来是筹备某个神秘比赛时想出来的 idea，当时想申请 rated，对着知识点瞪发现没有字符串（因为我非常不会），然后当时那个位置的题目背景指向是道构造，因此就想了这么个题。后来因为最难的题核心 idea 撞车了整个比赛拆掉了。那场比赛筹备时的另一个 idea 被出成了 P11887，我也很喜欢那个 idea，欢迎去做一做（广告）。很可惜当时急着想出出来因此没能出成月赛让更多人见到/ng

正好构造也很符合这个位置的背景，于是就丢这了。本来其实歌名选的是 3-8 字，后来感觉白色风车放 B 太难了，这题放 D 又太超纲且也可能偏难，因此忍痛舍弃了 8 字，这下组题舒服了。

性质 A

由于 p_i\le1，因此可以直接得出 S_i 与 T_1 是否相同，且发现 m=1。容易解决以上问题。

性质 B

事实上此时 p 数组就是扩展 KMP 中求出的 z 数组。个人感觉和正解没有本质的难度差异，但是会少一些细节，并且给没了解过 p 数组但知道 z 数组的选手一些提示（有吗？）

性质 C

在染色时会更加容易，只需要解决字符串部分就能做。其余部分包括建图都和正解一样，图二染色的判定和求方案数是简单的。（好像拿这部分分的人比会 n^2 弦图做法的少？）

正解

首先题目给出的就是 P5410 扩展 KMP 模板里的 p 数组。显然 i+p_i>n 时无解。

则 T 的 z 数组可由 p 数组求出。朴素地匹配即可做到 O((n+m)m)，以下给出 O((n+m)\alpha(n+m)) 的匹配方法。

模拟求 z 函数的过程。维护 z-box [l,r)。

• 如果 i\ge r，朴素地匹配，有 T_{i+j}=T_j。用并查集维护等价类，以下相同。
• 否则 i<r，此时有：
  • 若 z[i-l]<r-i，则要求 z[i]=z[i-l]，若不满足则无解。
  • 若 z[i-l]\ge r-i，则要求 z[i]\ge r-i，若不满足则无解。否则匹配，T_{r+j}=T_{r-i+j}。

判定及维护后同样更新 z-box。

继续模拟求 p 数组的过程，维护 z-box [l,r)。若在同一等价类中则出现矛盾无解，否则可在等价类间连边。

• 如果 i\ge r，则 S_{i+j}=T_j。
• 否则 i<r，此时有：
  • 若 z[i-l]<r-i，则要求 p[i]=z[i-l]，若不满足则无解。
  • 若 z[i-l]\ge r-i，则要求 p[i]\ge r-i，若不满足则无解。否则匹配，S_{r+j}=T_{r-i+j}。

以上过程总复杂度为 O((n+m)\alpha(n+m))，瓶颈在并查集。

同时要求 T_{i+z[i]}\neq T_{z[i]} 且 S_{i+p[i]}\neq T_{p[i]}，将不等关系两侧的等价类连边，若存在自环则代表出现矛盾，无解。

接下来要做的就是在建出来的图上求 c 种颜色的染色方案数。显然这在一般图上是 NP-hard 的，但是我们知道有一个东西叫做弦图。

先只看 T 建出的图。考虑一个长大于 3 的环，这个环上一定有一个编号最大的点，由于 T 连出所有边都形如 (i+z[i],i)，因此这个最大的点 k 处一定满足 \exists i<j,k=i+z[i]=j+z[j]，根据 z 函数的定义，有 T_{[i,k-1]}=T_{[0,z[i]-1]}，故 T_{[0,z[j]-1]}=T_{[j,k-1]}=T_{[j-i,z[i]-1]}。因此在上述过程中我们一定会比较 T_{z[i]} 与 T_{z[j]}，从而它们或者在同一等价类中，或者有连边。

再看加入 S 后的部分。由于所有边都连在 S_{i+p[i]} 与 T_{p[i]} 之间，故环上 S 中的点 k 处一定满足 \exists i<j,k=i+p[i]=j+p[j]，同样有 S_{[i,k-1]}=T_{[0,p[i]-1]}，故 T_{[0,p[j]-1]}=S_{[j,k-1]}=T_{[j-i,p[i]-1]}。故我们一定比较过 T_{p[i]} 与 T_{p[j]}。

我们于是证明了建出的图为弦图，其点数与边数均为 O(n+m)，朴素地求完美消除序列染色，由于在本题条件下构造出的图为稀疏图，而且极大团大约只有 \log 级别大小，具体地，构造出大小为 k 的团需要长为 2^{k-1} 的字符串。因此大概可以做到 O((n+m)\text{polylog})，具体没算，但大概也能过。

如果用 MCS 算法，此处有一个问题：算法的证明过程中用到了简单图的性质，而我们直接建图可能有重边。如果直接去重复杂度可能带 \log，虽然很小，大概也能过。。

这里有一个简单的解决办法：我们在求 label_x 时同时维护一个 vector，存储对 label_x 有贡献的点。由于我们每次用一个点扩展，容易发现在从 u 扩展的过程中只要判断 vector 中最新的一个点是否为 u 即可确定此边是否为不需计算的重边。构造染色方案的过程中也可以直接遍历该 vector 求颜色的 \operatorname{mex}，由于 \sum label_x 是 O(n+m) 的，因此这个算法的总复杂度仍为 O(n+m)。

彩蛋

样例第二组数据就是 P5410 的样例，找到了应该就能发现是同一个东西。出题人的提示真是太良心啦！