← 返回题目列表

Codeforces · 1499/E

E. 混沌合并

中文机器翻译题面 查看原题

给定两个字符串 $$$x$$$ 和 $$$y$$$,两者均仅包含小写拉丁字母。令 $$$|s|$$$ 为字符串 $$$s$$$ 的长度。

如果序列 $$$a$$$ 恰好由 $$$|x|$$$ 0 和 $$$|y|$$$ 1 以某种顺序组成,那么我们将其称为合并序列。

合并 $$$z$$$ 是根据以下规则从序列 $$$a$$$ 生成的:

- 如果 $$$a_i=0$$$,则从 $$$x$$$ 的开头删除一个字母并将其附加到 $$$z$$$ 的末尾;
- 如果 $$$a_i=1$$$,则从 $$$y$$$ 开头删除一个字母并将其附加到 $$$z$$$ 末尾。

如果存在某个位置 $$$i$$$ 使得 $$$a_i \neq b_i$$$ ,则两个合并序列 $$$a$$$ 和 $$$b$$$ 是不同的。

如果对于从 $$$2$$$ 到 $$$|z|$$$ $$$z_{i-1} \neq z_i$$$ 的所有 $$$i$$$,我们称字符串 $$$z$$$ 为混沌。

设 $$$s[l,r]$$$ 对于某些 $$$1 \le l \le r \le |s|$$$ 是 $$$s$$$ 的连续字母的子串,从位置 $$$l$$$ 开始,到位置 $$$r$$$ 结束(含)。

令 $$$f(l_1, r_1, l_2, r_2)$$$ 为 $$$x[l_1,r_1]$$$ 和 $$$y[l_2,r_2]$$$ 产生混沌合并的不同合并序列的数量。请注意,仅考虑 $$$x$$$ 和 $$$y$$$ 的非空子字符串。

计算$$$\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)$$$ 与 $$$1 \le l_1 \le r_1 \le |x|$$$ 和 $$$1 \le l_2 \le r_2 \le |y|$$$ 模 $$$998\,244\,353$$$ 的总和。

示例

输入 #1

aaa
bb

输出 #1

24

输入 #2

code
forces

输出 #2

1574

输入 #3

aaaaa
aaa

输出 #3

0

输入#4

justamassivetesttocheck
howwellyouhandlemodulooperations

输出#4

667387032

注意

在第一个示例中有:

- $$$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$$$。