二进制 Shuffle Square 判定次指数做法
xiao7_Mr_10_
·
2026-11-19 19:57:56
·
算法·理论
前言
提示:本文由 AI 生成,尚未严格检验其正确性。
前情提要。
ps:本人没有 github 账号,所以想要原文稿的话可以私信。
从 1.152593^n 到次指数:二进制 Shuffle Square 判定
给你一个 01 串,把每个位置染成红色或蓝色。红色字符按原顺序读出来,蓝色字符也按原顺序读出来,能不能让读到的两个串完全一样?
例如 \texttt{00101101} 可以把第 1,3,4,6 个位置染红,其余染蓝。两边读出来都是 \texttt{0101} 。这个公共串叫作根 ,原串叫作一个 shuffle square 。这种判定在二进制字母表上已经是 NP 完全的 [1]。
最直接的做法是枚举根。设输入长度为 n=2m ,根的长度就是 m 。固定一个候选根之后,用二维 DP 记录它的两个副本各读了几个字符,就能判断原串是否由它们交错而成。候选根有 2^m 个,时间是 O^*(2^{n/2}) ,底数约为 1.414214 。本文的 O^* 隐去关于 n 的多项式因子。奇数长度直接判无解,空串判有解。
下面讲同一道题的两条路线。第一条保留队列状态,但用一个三维 DP 跳过最难枚举的那段队列,得到 O^*(1.152593^n) 。第二条把一个未知解画成平面图,再借平面分隔定理做分治,待审阅稿给出的上界为 2^{O(\sqrt n\log n)} 。两条路线都能还原染色。
一、从左往右看,真正需要记住的是哪段字符
在一个合法染色里,两种颜色各读到的串,都是根的前缀。如果红色读了 a 个字符,蓝色读了 b 个,且 a\ge b ,那么红色多出来的正好是根的第 b+1 到第 a 个字符。把这段记作队列 Q 。
能否一直把红色当作领先的一方?可以。把一份合法染色在两色计数相等的位置切成若干段。每段的开头和结尾,两色都读到了根的同一个前缀,因此这段内两色读出的子序列相同。如果某段中蓝色领先,就整段交换红蓝。这样得到的解满足每个前缀里红色至少和蓝色一样多。
于是有两种转移。
当前字符染红,把它放到队尾。
当前字符染蓝,要求它等于队首,然后弹出队首。
对应的不变量是「已经读到的红色串 = 已经读到的蓝色串 + Q 」。从空队列开始,最后回到空队列,就得到一份合法染色。同层相同的队列只需保留一个,因为后续转移只看队列内容和还没读的输入。He 和 Post 在 [4] 中也用过这个队列模型,称为 buffer thread 。
如果只找队列始终短于 h 的解,长度从 0 到 h-1 的二进制队列总共只有 2^h-1 种,时间是 O^*(2^h) 。剩下的问题是,遇到必须经过长队列的解,有没有办法只知道它的长度,而不用猜出里面的每一个字符?
二、队列很长时,把它留给匹配 DP
对任何未被短队列 DP 覆盖的解,队列长度至少有一次恰好等于 h ,因为每一步只会加一或减一。枚举这个时刻读完的位置 t 。左侧正向扫描,右侧倒着扫描并交换红蓝。
为什么右侧也能这样扫?设切点处红、蓝分别读了 a,b 个字符。右侧倒着读时,交换后的红、蓝分别读了 m-b,m-a 个字符,差仍为 a-b 。对任意切点都是如此,因此反向交换后的扫描也满足红色始终领先或持平。两端在切点留下的队列,分别是根的第 b+1 到第 a 个字符及其反串。
记两侧的出队次数为 d_L,d_R 。由于每侧的「入队数减出队数」都等于 h ,有
d_L=\frac{t-h}{2},\qquad d_R=\frac{n-t-h}{2},\qquad d_L+d_R=m-h.
只枚举使两者都是非负整数的切点。上式最后一项很有用。对固定的 h ,无论切点在哪,两边合计处理的出队次数都是 m-h 。
在第 d 次入队之后再切一刀
单看某一侧,记它一共出队 d 次。FIFO 意味着被弹出的是最先入队的 d 个字符。现在把扫描过程切在第 d 次入队刚结束 的位置,记此时的队列为 U ,余下的输入为 W 。若 d=0 ,就在开头切,令 U 为空。
从这里到两侧相遇前,W 里的字符只做两件事。
出队字符按顺序弹掉 U 中的全部字符。
新入队的字符全部活到相遇时,按顺序组成公共残余串 Q 。
所以 W 恰好是 U 与 Q 的交错。反过来,给定这样的交错,把对应 U 的字符执行出队,把对应 Q 的字符执行入队。尚未弹完的 U 一直位于新字符前面,每次出队都合法。
右侧同理。把右侧切出来的两个串翻回原方向,问题就变成,从 W_L 删去子序列 U ,同时从 W_R 删去子序列 V ,能否使两边剩下同一个长度为 h 的串?
还是用 \texttt{00101101} 的染色,在第 4 个位置后切开。这时 h=2 ,两个方向各出队一次。两边都在自己的第一次入队后再切一次,得到下表。右侧一行已经翻回原方向。
一侧
剩余输入
指定删除的子序列
删除后留下的串
左
\texttt{010}
\texttt{0} ,删第一个字符
\texttt{10}
右
\texttt{110}
\texttt{1} ,删第二个字符
\texttt{10}
两边一起读,剩下的字符同步通过
设状态为 (i,j,k) 。左边已经删了 U 的前 i 个字符,右边已经删了 V 的前 j 个字符,两边已经同步保留了 k 个字符。接下来要看的位置是 W_L 的第 i+k+1 个、W_R 的第 j+k+1 个。
如果左侧当前字符等于 U 的下一个字符,可以令 i\gets i+1 。
如果右侧当前字符等于 V 的下一个字符,可以令 j\gets j+1 。
如果两边当前字符相等且 k<h ,可以同步保留它们,令 k\gets k+1 。
每个转移都要求读取的位置存在。终点是 (|U|,|V|,h) 。任意一条到终点的路径都给出两次删除方案。反过来,如果存在合法删除方案,就可以依次删掉下一个公共字符之前的指定字符,再同步保留公共字符,最后处理各自的尾部。因此三维 DP 恰好判定能否拼接,单次最多 O(n^3) 时间。
设 L_0,L_1,R_0,R_1 是左右两侧按原方向读出的两色子序列,0 表示红色。左侧残余为 Q ,右侧反向残余为 Q^{\mathrm{rev}} ,所以
L_0=L_1Q,\qquad R_1=Q R_0
\quad\Longrightarrow\quad L_0R_0=L_1R_1.
记下外侧队列 DP 和内侧三维 DP 的前驱即可还原染色。左侧保留的字符染红、删除的字符染蓝,右侧在原方向下恰好相反。
三、黄金分割常数从哪里来
现在只剩下外侧候选 U,V 的费用。若一侧需要找到第 d 次入队的位置,就跑分层队列 DP。读了 i 个字符、队列长为 \ell 时,入队次数是 (i+\ell)/2 。一次转移达到第 d 次入队时,把该层位置和队列记作候选,然后停止扩展这条分支。同一层保留一个相同队列的代表即可。不同切点的余串 W 不同,要分别保留。
若已经入队 p 次、出队 q 次,总共就读了 p+q 个字符。队列里的字符都在最早的 q 次入队之后才入队,所以它们的位置都大于 q 。于是队列内容是当前扫描方向下,固定后缀 S[q+1\,..\,p+q] 的一个子序列。这个后缀的长度恰好是 p 。
Hirschberg 和 Régnier 在 [2] 研究了固定长度子序列的计数。这里需要把所有长度加在一起。对任一子序列,总在当前可用区间内取它下一个字符的最早出现位置,每一步只记录以下两种选择。
取当前第一个字符,消耗一个位置。
取与当前第一个字符相反的字符,至少消耗两个位置。
字母表只有两个字符,给定原串和这串选择,就能确定每一步取什么。给第一种选择记费用 1 ,第二种记费用 2 ,总费用至多 p 。费用恰好为 r 的选择串数满足 f_r=f_{r-1}+f_{r-2} ,其中 f_0=f_1=1 。对 0\le r\le p 求和仍是 O(\varphi^p) ,其中 \varphi=(1+\sqrt5)/2 。
外侧 DP 的每层都满足 p\le d 。加上多项式数量的层,一侧至多生成 O^*(\varphi^d) 个候选,生成时间也在同一个界内。固定主切点 t ,两侧候选的配对数因此是
O^*\!\left(\varphi^{d_L}\varphi^{d_R}\right)=O^*\!\left(\varphi^{m-h}\right).
每对只跑一次多项式时间的匹配,枚举主切点也只乘一个多项式因子。两种情况合起来,时间是 O^*(2^h+\varphi^{m-h}) 。
$$
h=\frac{m\log\varphi}{\log(2\varphi)},\qquad
2^h=\left(2^{\frac{\log\varphi}{2\log(2\varphi)}}\right)^n.
$$
把 $h$ 取最近的整数并限制在 $[1,m]$,只影响常数因子。括号里的数约为 $1.1525926768$,于是确定性时间上界为 **$O^*(1.152593^n)$**。用确定性字典合并同层状态,每次只测试一对候选,空间也在这个界内。
## 四、一份解里有两种相邻关系
队列做法从输入顺序出发。若改从**根下标顺序**出发,一份合法解可以理解为给根的每个下标 $i$ 找两份出现,记为 $A_i,B_i$。输入串就是这两排出现的一次交错。
还是用开头的例子。如果把每个字符换成它的副本名与根下标,得到
$$
A_1,\ B_1,\ A_2,\ A_3,\ B_2,\ A_4,\ B_3,\ B_4.
$$
在根下标上建一个图 $G$,有两类边。
1. 在根下标顺序里,相邻的下标连边。
2. 在输入顺序里,相邻位置所对应的下标连边。删掉自环和重边。
第一类边看起来只是一条链,却有独立的作用。接下来我们要同时切开**根的顺序**和**输入的顺序**。例子里若删去下标 $2$ 以及它在输入中的两次出现,那么:
| 顺序 | 删除后的连续段 | 分组 |
| :--- | :--- | :--- |
| 根下标顺序 | $[1]$、$[3,4]$ | $\{1\}$ 和 $\{3,4\}$ 各一组 |
| 输入顺序 | $A_1 B_1$、$A_3$、$A_4 B_3 B_4$ | 第一段属前一组,后两段属后一组 |
输入中的同一组可以有不止一段。只要每段内部都属于同一组,搜索时就能按段分配。
## 五、为什么这张图是平面图
直接把同下标的两个点合到一起,图容易画乱。先把 $A_1,\ldots,A_m$ 从左到右放在矩形上边,把 $B_1,\ldots,B_m$ 同样从左到右放在下边。
根顺序的边沿两行画。输入中相邻而且同色的两个位置也是同一副本中的相邻下标,已经有对应的边。剩下的输入相邻边都跨越两行,把它们画成矩形内部的直线。
按这些相邻边在输入中出现的顺序看,上端点下标不下降,下端点下标也不下降。理由是每种颜色的出现位置都按该副本的下标递增,两个输入相邻对至多共享一个端点。因此两条跨行边可以共享端点,却不会在内部交叉。
最后还要合并 $A_i,B_i$。沿矩形边界走一圈,顺序是
$$
A_1,A_2,\ldots,A_m,B_m,B_{m-1},\ldots,B_1.
$$
配对 $A_iB_i$ 在这个边界顺序中层层嵌套。把这些配对边画到矩形**外面**,就能同时避开彼此和内部的跨行边。收缩配对边后,删掉自环和重边,得到的就是 $G$。因此每一份合法解都给出一张平面图。
## 六、图由答案决定,怎么用它来找答案
Lipton 和 Tarjan 的平面分隔定理 [5] 保证,一张有 $m$ 个点的平面图可以分成 $D,X,Y$ 三组。分隔集 $D$ 至多有 $\sqrt{8m}$ 个点,$X,Y$ 各至多有 $2m/3$ 个点,而且 $X,Y$ 之间没有边。
这张图由未知解决定,但算法只需要**枚举分隔点及它们的两份出现**。固定一个猜测之后:
- 从根顺序删去 $D$,剩下至多 $|D|+1$ 段。对正确的猜测,每段内部的相邻下标由第一类边连着,所以整段只属于 $X$ 或只属于 $Y$。
- 从输入顺序删去 $D$ 的 $2|D|$ 个位置,剩下至多 $2|D|+1$ 段。对正确的猜测,一段内相邻位置的下标相等或由第二类边连着,所以整段也只属于一边。
这里的「段」按**删除前的当前顺序**切开。刚删掉的点两边即使后来接在一起,也还是两段。
递归时,每个子问题维护一列原根下标和一列原输入位置,都保持原来的相对顺序。每个下标在 $A,B$ 两个副本里各带一个允许的位置区间。初始时所有区间都覆盖整个输入,递归时只能收紧。
1. 枚举 $D$ 及每个 $s\in D$ 的位置 $p_{A,s},p_{B,s}$。所有这些位置必须互异,同下标的两个字符必须相等,同一副本内的位置按下标递增,并且满足已有的允许区间。
2. 枚举每个根段、每个输入段归哪个子问题。记当前根长为 $m$,两边的根长都须至多 $\lfloor 2m/3\rfloor$,输入位置个数须恰好为各自根长的两倍。
3. 对每个剩余下标 $j$,在每个副本中找到左右最近的分隔下标,要求 $j$ 的位置严格夹在它们的出现位置之间。缺了哪一侧就省去对应的界。把得到的新区间和原区间取交。
4. 递归求解。如果两个子问题都成功,就合并它们的染色和刚才猜定的染色。根很短时直接枚举染色并检查区间限制。
### 为什么两个子问题的解能直接拼起来
固定一个副本,检查任意两个下标 $j<k$。如果两者在同一个子问题里,顺序由递归保证。如果两者分属不同子问题,它们必在不同的根段,中间隔着某个 $s\in D$。刚传下去的约束保证 $j$ 的位置在 $p_{c,s}$ 之前、$k$ 的位置在它之后。若其中一个就是分隔点,直接由猜测检查或区间约束保证。所有位置恰好被使用一次,每个下标的一对字符也相同,因此拼出的染色合法。
再检查会不会漏掉解。固定任一满足当前约束的解。它对应的平面图有一个符合要求的分隔集,这个集合及其位置会被枚举到。刚才的两条分段性质保证,正确解两边的根和输入都能按段分过去。原解限制到两个子问题之后,仍满足所有新旧约束,所以递归不会漏掉它。这个论证在受约束的子问题里同样适用,因为平面性只用到了两种相对顺序。
## 七、每一层到底花多少时间
记 $d=|D|=O(\sqrt m)$。分隔下标有至多 $m^d$ 种选法,它们的两份出现有至多 $(2m)^{2d}$ 种选法。再给至多 $3d+2$ 个根段和输入段分组,总共增加至多 $2^{3d+2}$ 倍。加上枚举 $d$ 和多项式时间的检查,每个结点的本地工作量与分支数都可以界在 $2^{O(\sqrt m\log m)}$。
每个猜测最多产生**两次**递归求解。两边的解可以直接拼接,所以费用是相加。沿递归树往下看,第 $\ell$ 层的单个问题至多还剩 $(2/3)^\ell m$ 个根下标。把各层的分支数相乘时,指数部分满足
$$
\sum_{\ell\ge 0} O\!\left(\sqrt{(2/3)^\ell m}\,\log m\right)
=O(\sqrt m\log m).
$$
两次调用的常数因子以及递归深度带来的多项式因子都能并入这个界。代入 $m=n/2$,得到草稿中的确定性时间上界 **$2^{O(\sqrt n\log n)}$**。深度优先枚举,每层只保存当前猜测、位置区间和暂存的子问题解,所需空间为多项式。平面图部分只用字符相等性,因此这个论证也适用于字符可在多项式时间内比较的更大字母表。
## 八、两个上界该怎么读
队列法把**枚举长残余串**换成了同步匹配。平面分隔法把**给剩下每个位置分组**换成了给连续段分组。前一个改动降低了指数底数,后一个改动把主导枚举的量降到了 $O(\sqrt n)$ 个分隔下标及其出现位置。
因为 $\sqrt n\log n=o(n)$,次指数稿的上界在渐近意义下低于任意固定的 $c^n$($c>1$)。但对 $n=100$ 的评测,只要多猜几个分隔点、每个点再猜两份位置,分支就已经很多。此前直接枚举分隔点的实现在评测中超时。次指数篇目前是待审阅稿,正文把平面性、分段性质和拼接条件分开写,便于读者核查。
文献 [3] 和 [4] 还研究了随机二进制串里 shuffle square 有多常见。[4] 证明长度趋于无穷的偶长二进制串约有一半是 shuffle square。本文的两个界衡量的是**给定某一个输入时,最坏需要多少时间才能判定并构造**。
## 参考文献
1. L. Bulteau and S. Vialette. *Recognizing binary shuffle squares is NP-hard*. Theoretical Computer Science, 806, 116–132, 2020. [DOI](https://doi.org/10.1016/j.tcs.2019.01.012)
2. D. S. Hirschberg and M. Régnier. *Tight Bounds on the Number of String Subsequences*. Journal of Discrete Algorithms, 1(1), 123–132, 2000. [PDF](https://www.ics.uci.edu/~dan/pubs/JDA.pdf)
3. X. He, E. Huang, I. Nam, and R. Thaper. *Shuffle squares and reverse shuffle squares*. European Journal of Combinatorics, 116, 103883, 2024. [DOI](https://doi.org/10.1016/j.ejc.2023.103883)
4. X. He and L. Post. *Asymptotically half of binary words are shuffle squares*. arXiv:2512.12077v1, 2025. [预印本](https://arxiv.org/abs/2512.12077v1)
5. R. J. Lipton and R. E. Tarjan. *A Separator Theorem for Planar Graphs*. SIAM Journal on Applied Mathematics, 36(2), 177–189, 1979. [DOI](https://doi.org/10.1137/0136016)