E. Chaotic Merge
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\).
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\).
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\).