CF1499E Chaotic Merge

给定两个字符串 $x$ 和 $y$，均只包含小写拉丁字母。记 $|s|$ 为字符串 $s$ 的长度。 我们称一个序列 $a$ 为合并序列，如果它恰好包含 $|x|$ 个 $0$ 和 $|y|$ 个 $1$，顺序任意。 通过如下规则，可以用序列 $a$ 生成一个合并字符串 $z$： - 如果 $a_i=0$，则从 $x$ 的开头移除一个字母，并将其添加到 $z$ 的末尾； - 如果 $a_i=1$，则从 $y$ 的开头移除一个字母，并将其添加到 $z$ 的末尾。 如果存在某个位置 $i$ 使得 $a_i \neq b_i$，则两个合并序列 $a$ 和 $b$ 被认为是不同的。 我们称字符串 $z$ 为“混乱的”，如果对于所有 $i$ 满足 $2 \le i \le |z|$，都有 $z_{i-1} \neq z_i$。 记 $s[l,r]$ 表示字符串 $s$ 的一个子串，包含从位置 $l$ 到 $r$ 的连续字母（$1 \le l \le r \le |s|$）。 定义 $f(l_1, r_1, l_2, r_2)$ 为用 $x[l_1,r_1]$ 和 $y[l_2,r_2]$ 生成混乱合并字符串的不同合并序列的数量。注意，只考虑非空子串。 计算 $\sum \limits_{1 \le l_1 \le r_1 \le |x| \\ 1 \le l_2 \le r_2 \le |y|} f(l_1, r_1, l_2, r_2)$。输出答案对 $998\,244\,353$ 取模。

第一行输入字符串 $x$（$1 \le |x| \le 1000$）。 第二行输入字符串 $y$（$1 \le |y| \le 1000$）。 两个字符串均只包含小写拉丁字母。

输出一个整数，表示所有 $f(l_1, r_1, l_2, r_2)$ 之和，对 $998\,244\,353$ 取模。

在第一个样例中，有： - $6$ 对子串 "a" 和 "b"，每对有合法合并序列 "01" 和 "10"； - $3$ 对子串 "a" 和 "bb"，每对有合法合并序列 "101"； - $4$ 对子串 "aa" 和 "b"，每对有合法合并序列 "010"； - $2$ 对子串 "aa" 和 "bb"，每对有合法合并序列 "0101" 和 "1010"； - $2$ 对子串 "aaa" 和 "b"，每对没有合法合并序列； - $1$ 对子串 "aaa" 和 "bb"，有合法合并序列 "01010"； 因此，答案为 $6 \cdot 2 + 3 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 0 + 1 \cdot 1 = 24$。 由 ChatGPT 4.1 翻译