CF794G 题解

I_like_magic · 2025-03-26 20:09:30 · 题解

这题其实不难。

Update 2025.3.26：修改题解 Markdown。

Update 2025.3.27：修改题解中错误的式子，并重写逻辑清晰的代码。

Part 1.

首先，考虑没有 ? 如何做。

分两种情况：

• 字符串 x 与 y 长度相等。
• 字符串 x 与 y 长度不相等。

先考虑 x 和 y 长度不相等怎么做。

首先，将两个串中共同的字符删除。

比如 ABBAAA 和 BABBB，两个串有一个共同的 A，两个共同的 B，删除之后变为 AAA 和 BB。

那么显然，01 串 s 与 t 的长度比为 2:3

设 s 为 \overline{ab}，t 为 \overline{cde}，a,b,c,d,e 为长度相等的 01 串。

替换一下 x 和 y。

ABBAAA 变为 \overline{abcdecdeababab}。

BABBB 变为 \overline{cdeabcdecdecde}。

如果要让替换后的 01 串相等，那么我们需要保证 a = b = c = d = e。

如果我们多观察一下别的 x 和 y，使用相同的步骤操作，我们会发现，若 s 和 t 长度最简比为 a:b，那么那么 s = aE，t = bE。

其中 E 是一个 01 串。kE 表示 k 个 E 拼接在一起。

由于 s 和 t 的长度限制是 n，那么 E 的长度限制就是 len = \lfloor\frac{n}{\max\{a, b\}}\rfloor。

我们求出长度小于等于 len 的非空 01 串即为这种情况的答案。

答案 = 2^{len + 1} - 2。

注意如果 x 或者 y 在删除共同字符之后为空，那么无解。

接下来考虑 x 和 y 长度相等怎么做。

这种情况还要再细分。

• 显然，$s$ 和 $t$ 可以任意取。 答案为 $(2^{n + 1} - 2)^2$。
• 这种情况 $s$ 和 $t$ 的**长度**仍然是可以任取，但是由于 $x$ 和 $y$ 不相同，那么必然会有某些位置 $x_i =$ `A`，$y_i =$ `B`（或相反），那么 $s$ 和 $t$ 中必然会有一个串是另一个串的前缀。 然后，举个例子，$s$ 长度为 $6$，$t$ 长度为 $4$。设 $s = \overline{abcdef}, t = \overline{abcd}$。 > $\texttt{abcdef{\color{red}{abcd}}}

  \texttt{abcd{\color{red}{abcd}}}

  标红是因为无论后面接上的是 s 还是 t，前四个都一定是 \overline{abcd}。那么可以得出 e = a, f = b, a = c, b = d。

  那么 a = c = e 并且 b = d = f。

  所以 s = \overline{ababab}, t = \overline{abab}。

  简单证明或者感性理解即可得知：s 和 t 的最长重复单元长度为：\gcd(|s|, |t|)。

  那么答案即为 \sum\limits_{a = 1}^{n}\sum\limits_{b = 1}^{n}2^{\gcd(a, b)} = \sum\limits_{k = 1}^{n}(2^k(2\sum\limits_{j = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_j - 1))（推式子见结尾）。

  前缀和处理 \sum\limits_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\varphi_i 即可。

• 以上两种情况都不符合。

  显然，对于这种情况，s 一定等于 t。

  那么答案为 2^{m + 1} - 2。

以上解决了无 ? 的情况。

Part 2.

现在解决有 ? 的情况。

分两种情况：

• 字符串 x 与 y 长度相等。
• 字符串 x 与 y 长度不相等。

还是先考虑 x 和 y 长度不相等怎么做。

首先，我们计算出 x 与 y 中含有的 A 和 B 的差。

设 cnt_{x, A} 表示 x 中 A 的个数，其他同理。

那么：记 A 个数差 d_A = cnt_{x, A} - cnt_{y, A}，B 个数差 d_B = cnt_{x, B} - cnt_{y, B}。

然后，我们考虑最边界的情况，x 中的所有 ? 设为 A；y 中的所有 ? 设为 B。

那么：

接下来，我们考虑修改问号的值会发生什么。

举个例子：

为方便染色，使用 \LaTeX。

\texttt{AAB?B?A} \texttt{B?ABBB?A}

变为边界情况：

\texttt{AAB{\color{red}{A}}B{\color{red}{A}}A} \texttt{B{\color{red}{B}}ABBB{\color{red}{B}}A}

接下来我们以这个状态为基准，我们发现，翻转任意一个标红字母（将 A 变为 B，或相反），对 d_A 和 d_B 的影响都是一样的。

将 x 中的 A 变为 B，会导致 d_B 加一，而 A 的数量减一，d_A 减一。

若将 y 中的 B 变为 A，同样会导致 d_B 加一，d_A 减一。

那么我们可以枚举有多少个字母从基准状态翻转了。

标红字母个数为 cnt_?，翻转字母数量为 k，那么总共可能的情况有 C_{cnt_?}^{k} 种，d_A' = d_A - k，d_B' = d_B + k。

然后我们考虑每组 d_A' 和 d_B' 怎么计算贡献。

如果 d_A' \times d_B' \ge 0，那么则代表两者同号或有一项等于 0，那么就对应了这种情况：

注意如果 x 或者 y 在删除共同字符之后为空，那么无解。

只有两者异号，才能产生贡献。

然后两者异号，就可以直接用上面的无 ?、x,y 不等长解决。