Chaotic Merge

题意翻译

给定两个仅由小写字母组成的字符串 $x$ 和 $y$。 如果一个序列仅包含 $|x|$ 个 $0$ 和 $|y|$ 个 $1$，则称这个序列为合并序列。 字符串 $z$ 初始为空，按如下规则由合并序列 $a$ 生成： - 如果 $a_i=0$，则把 $x$ 开头的一个字符加到 $z$ 的末尾； - 如果 $a_i=1$，则把 $y$ 开头的一个字符加到 $z$ 的末尾。 两个合并序列 $a$ 和 $b$ 被认为是不同的，如果存在某个 $i$，使得 $a_i\neq b_i$。 若一个字符串任意两个相邻位置上的字符都不同，则我们称该字符串是混乱的。 定义 $f(l_1,r_1,l_2,r_2)$ 表示能从 $x$ 的子串 $x[l_1,r_1]$ 和 $y$ 的子串 $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)$，答案对 $998244353$ 取模。

题目描述

You are given two strings $ x $ and $ y $ , both consist only of lowercase Latin letters. Let $ |s| $ be the length of string $ s $ . Let's call a sequence $ a $ a merging sequence if it consists of exactly $ |x| $ zeros and exactly $ |y| $ ones in some order. A merge $ z $ is produced from a sequence $ a $ by the following rules: - if $ a_i=0 $ , then remove a letter from the beginning of $ x $ and append it to the end of $ z $ ; - if $ a_i=1 $ , then remove a letter from the beginning of $ y $ and append it to the end of $ z $ . Two merging sequences $ a $ and $ b $ are different if there is some position $ i $ such that $ a_i \neq b_i $ . Let's call a string $ z $ chaotic if for all $ i $ from $ 2 $ to $ |z| $ $ z_{i-1} \neq z_i $ . Let $ s[l,r] $ for some $ 1 \le l \le r \le |s| $ be a substring of consecutive letters of $ s $ , starting from position $ l $ and ending at position $ r $ inclusive. Let $ f(l_1, r_1, l_2, r_2) $ be the number of different merging sequences of $ x[l_1,r_1] $ and $ y[l_2,r_2] $ that produce chaotic merges. Note that only non-empty substrings of $ x $ and $ y $ are considered. Calculate $ \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) $ . Output the answer modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains a string $ x $ ( $ 1 \le |x| \le 1000 $ ). The second line contains a string $ y $ ( $ 1 \le |y| \le 1000 $ ). Both strings consist only of lowercase Latin letters.

输出格式

Print a single integer — the sum of $ f(l_1, r_1, l_2, r_2) $ over $ 1 \le l_1 \le r_1 \le |x| $ and $ 1 \le l_2 \le r_2 \le |y| $ modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

aaa
bb

输出样例 #1

24

输入样例 #2

code
forces

输出样例 #2

1574

输入样例 #3

aaaaa
aaa

输出样例 #3

0

输入样例 #4

justamassivetesttocheck
howwellyouhandlemodulooperations

输出样例 #4

667387032

说明

In the first example there are: - $ 6 $ pairs of substrings "a" and "b", each with valid merging sequences "01" and "10"; - $ 3 $ pairs of substrings "a" and "bb", each with a valid merging sequence "101"; - $ 4 $ pairs of substrings "aa" and "b", each with a valid merging sequence "010"; - $ 2 $ pairs of substrings "aa" and "bb", each with valid merging sequences "0101" and "1010"; - $ 2 $ pairs of substrings "aaa" and "b", each with no valid merging sequences; - $ 1 $ pair of substrings "aaa" and "bb" with a valid merging sequence "01010"; Thus, the answer is $ 6 \cdot 2 + 3 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 0 + 1 \cdot 1 = 24 $ .