混乱合并 题解

思路

令 $a_i$ 表示以 $x_i$ 结尾的混乱非空子串数量，$b_j$ 同理。它们分别是对应位置的最长相邻不同后缀长度。

令 $dp^x_{i,j}$ 表示已经使用两个非空子串、横纵端点为 $i,j$，且最后一个字符取自 $x_i$ 的合并数；$dp^y_{i,j}$ 类似。追加 $x_i$ 时，前一字符可能是 $x_{i-1}$ 或 $y_j$，并需与 $x_i$ 不同；若这是第一个来自 $x$ 的字符，则此前可取任意以 $y_j$ 结尾的混乱子串，共 $b_j$ 种。另一方向对称。

做法

子任务 1 枚举两子串和所有二进制合并序列，直接检查结果串。

子任务 2 固定两个子串左端点，在后缀网格上做动态规划并累加所有右端点，复杂度 $O(|x|^2|y|^2)$。

满分算法把所有左端点的贡献合并进 $a_i,b_j$ 和上述二维状态，每个网格点只转移常数次。

正确性证明

任一合法合并的最后一步唯一地取自 $x$ 或 $y$。若最后取自 $x_i$，删去它后，要么仍是已经使用两串且末尾为 $x_{i-1}$ 或 $y_j$ 的合法合并，要么尚未使用 $x$、只是一段以 $y_j$ 结尾的混乱子串。转移按末尾字符不同的必要充分条件加入这些且仅这些方案；$y$ 方向同理。因此每个合法合并按唯一末步被计数一次，累加所有端点得到题目所求。

复杂度

时间复杂度 $O(|x||y|)$，空间复杂度 $O(|y|)$。