ARC181 - B - Annoying String Problem

B - 令人讨厌的字符串问题 编辑：evima

在大多数情况下，\(f(S,T,X)\) 和\(f(S,T,Y)\) 的长度相等，这揭示了\(T\) 的长度。让我们来看看当已知 \(S\) 和 \(T\) 的长度时，在什么条件下 \(S\) 和 \(T\) 满足 \(f(S,T,X)=f(S,T,Y)\)。

例题

例如，当\(|S|=6\)和\(|T|=4\)时，让我们考虑当\(S+T+T+S+T+S=T+T+T+S+T+T+T\)成立时的情况。通过比较开头，需要 \(T\) 是 \(S\) 的前缀，并且 \(S\) 可以用 \(S'\) 表示为 \(S=T+S'\)，\(|S'|=2\)。将其代入等式，我们得到：

\(T+S'+T+T+T+S'+T+T+S' = T+T+T+T+S'+T+T+T\)

\(\iff S'+T+T+T+S'+T+T+S' = T+T+T+S'+T+T+T\)。

接下来，\(S'\) 必须是\(T\) 的前缀，而\(T\) 可以用\(T'\) 表示为\(T=S'+T'\)，\(T'||=2\)。将其替换到等式中，我们得到

\(S'+\)（\(S'\) 和 \(T'\) 的表达式）\(=T'+\)（\(S'\)和 \(T'\) 的表达式）。

在这个等式中，\(S'=T'\) 是必要且充分的，因为 \(|S'|\) 和 \(|T'|\) 相等。用 \(S'=T'=U\) 表示 \(S\) 和 \(T\) ，我们得到 \(S=U+U+U\) 和 \(T=U+U\) 。反之，如果 \(S\) 和 \(T\) 可以用这种方法表示，那么 \(S\) 和 \(T\) 的连接将是 \(U\) 的重复，从而使等式明显成立。因此

• \(|S|=6, |T|=4\), 以及 \(S+T+T+S+T+S=T+T+T+S+T+T\) \(\iff\) \(S\)和 \(T\)可以用长度为\(2\)的字符串\(U\)表示为\(S=U+U+U\)和\(T=U+U\)。

观察

推广上述过程，我们会发现

• 如果等式为三元形式，如 \(A+A+B=A+A+B\)，则对任意 \(A\) 和 \(B\) 都成立。
• 如果等式中使用的两个字符串 \(A\) 和 \(B\) 的长度不同（假设 \(|A| < |B|\)），则等式的形式为 \(A+(\dots)=B+(\dots)\)，此时需要 \(B=A+B'\)，从而将问题简化为关于 \(A\) 和 \(B'\) 的相同形式。
• 如果等式中使用的两个字符串 \(A\) 和 \(B\) 的长度相等，则 \(A=B\) 是必要且充分的。

特别是，第二次还原会重复进行，直到最终达到第一或第三状态。

考虑到通过重复还原达到的最终状态，第二次还原的形式如下：

• \(A+A+(\dots) = B+(\dots) \iff A + A + (\dots) = A + B' + (\dots) \iff A + (\dots) = B' + (\dots)\)
• \(A+B+(\dots) = B+(\dots) \iff A + A + B'+ (\dots) = A + B' + (\dots) \iff A + B' + (\dots) = B' + (\dots)\)

因此，如果初始方程不是三元形式，方程在第二次还原时就不会还原到第一种状态，而总是会到达第三种状态。

从第三状态追溯诸如\(B=A+B'\)这样的替换，有必要且充分条件是\(A\)和\(B\)是长度为\(L\)的共同字符串\(C\)的重复，其中\(L\)是第三状态中字符串\(A\)和\(B\)的长度。

因此，一旦确定了 \(L\)，就可以轻松检查条件。考虑到第二次还原过程中的长度变化，可以将其视为 \((n,m)\rightarrow (n,m-n)\) 一直重复到 \(n=m\)。这正是欧几里得算法，所以 \(L=\mathrm{gcd}(n,m)\)。

解法

首先，考虑 \(X\) 和 \(Y\) 中 1 的数量相等的情况。如果0的数量也相等，设置 \(T=S\) 显然满足 \(f(S,T,X)=f(S,T,Y)\)，所以答案是Yes。否则，\(f(S,T,X)\) 和\(f(S,T,Y)\) 的长度不可能相等，所以答案是No。

如果 \(X\) 和 \(Y\) 中的 1 数量不相等，我们就有 \(X\neq Y\)，\(|f(S,T,X)|=|f(S,T,Y)|\) 就会产生一个以 \(|T|\) 为单位的线性方程，让我们找到 \(|T|\)（如果这不是整数或为负数，答案就是No）。

根据上述观察，当 \(X\neq Y\)、

★ \(f(S,T,X)=f(S,T,Y) \iff S\) 和 \(T\) 是长度为 \(\mathrm{gcd}(|S|,|T|)\) 的字符串 \(U\) 的重复。

因此，如果 \(S\) 的周期为 \(\mathrm{gcd}(|S|,|T|)\)，那么满足条件的 \(T\) 就存在。这可以在 \(O(|S|)\) 时间内通过验证 \(S\) 的第 \(i\) 个字符是否等于第 \((i+\mathrm{gcd}(|S|,|T|))\) 个字符来检验。

★的正式证明：

通过对 \(||S|-|T||\) 的归纳来证明。当 \(|S|=|T|\) 时，证明就很清楚了。

假设 \(|S| < |T|\) 不失一般性。同时，由于 \(X \neq Y\)，通过去除所需的公共前缀，我们可以假设 \(X\) 和 \(Y\) 的第一个字符分别是 0 和 1。那么，\(S\)必须是\(T\)的前缀，并且存在\(T'\)，使得\(T=S+T'\)。为使等式成立，需要\(f(S,T',X')=f(S,T',Y')\)，其中\(X'\)和\(Y'\)分别是在\(X\)和\(Y\)中同时用01替换1得到的字符串。根据归纳假设，\(S\)和\(T'\)是长度为\(\mathrm{gcd}(|S|,|T|-|S|)=\mathrm{gcd}(|S|,|T||)\) 的字符串\(U\)的重复。结合 \(T=S+T'\)，可以看出 \(T\) 也是 \(U\) 的重复。这样，必然性就得到了证明。充分性显而易见。

通过www.DeepL.com/Translator（免费版）翻译