Chaotic Merge
Contest: Educational Codeforces Round 106 (Rated for Div. 2)
Difficulty rating: 2400
Tags: combinatorics, dp, math, strings

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

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
aaa
bb

Example output:
24

Example input:
code
forces

Example output:
1574

Editorial:
First, let's try to calculate the number of merging sequences just for some fixed pair of strings $$$x$$$ and $$$y$$$.
Imagine we build a merge letter by letter. So far $$$i$$$ letters are in the merge already. For the $$$(i+1)$$$-th letter we can pick a letter from either string $$$x$$$ or string $$$y$$$ (put a $$$0$$$ or a $$$1$$$ into the merging sequence, respectively). What constraints our choice? Easy to see that it's only the $$$i$$$-th letter of the merge. So we can come up with the following dynamic programming.
$$$dp[i][j][c]$$$ is the number of merging sequences such that $$$i$$$ characters from $$$x$$$ are taken, $$$j$$$ characters from $$$y$$$ are taken and the last character of the merge is $$$c$$$. $$$c$$$ can be either just a letter (a dimension of size $$$26$$$) or an indicator of a string the last character was taken from ($$$0$$$ for string $$$x$$$ and $$$y$$$ from string $$$y$$$). Since we know how many characters are taken from each string, we can easily decide the last taken character from that indicator. For each transition we can just take a character from either of the strings.
The sum of $$$dp[|x|][|y|][i]$$$ over all $$$i$$$ will be the total number of merging sequences.
Now for the substrings. Recall the following definition of a substring: $$$b$$$ is a substring of $$$a$$$ if you can remove some characters from the beginning of $$$a$$$ (possibly, none or all) and some characters from the end of $$$a$$$ (possibly, none or all) to get the string $$$b$$$.
What if we incorporated that definition into our dynamic programming? Let $$$dp[i][j][c]$$$ be the number of merging sequences that end exactly before the $$$i$$$-th character of $$$x$$$, exactly before the $$$j$$$-th character of $$$y$$$ and the last character is still $$$c$$$.
How to remove some characters from the beginning? That actually is the same as attempting to start the merge from every state of dp. So, if we are currently in some state $$$dp[i][j][c]$$$, then we can act as if we have just taken the $$$i$$$-th character of $$$x$$$ or the $$$j$$$-th character of $$$y$$$ as the first character of the merge.
How to remove some characters from the end? Since $$$dp[i][j][c]$$$ is the number of merging sequences that end exactly there, why not just sum up all the values of dynamic programming into the answer? We will count the sequences that end in all possible positions of both strings.
That is almost the answer to the task. The only issue we have is that we forgot the condition that asks us to get a non-empty substring from each string. Well, there are multiple ways to resolve the issue.
We can remove bad sequences afterwards: their count is the number of chaotic substrings of $$$x$$$ multiplied by all possible empty substrings of $$$y$$$ (there are $$$|y|+1$$$ of them) plus the same thing for $$$y$$$ and $$$x$$$. These can be counted with two pointers.
Alternatively, we can add an extra dimension or two to the dp to indicate if we have ever taken a character from $$$x$$$ and from $$$y$$$. So we get $$$dp[i][j][c][fl_x][fl_y]$$$ with $$$fl_x$$$ and $$$fl_y$$$ being binary flags that tell if a character from $$$x$$$ and from $$$y$$$ was ever taken. That way we can only push the states with both flags set to true to the answer.
Overall complexity: $$$O(|x| \cdot |y|)$$$.