P10694 [SNCPC2024] Twin Subsequences

Little L feels very uncomfortable when he sees strings he dislikes. He also feels uncomfortable when he sees them appear as subsequences. Given a long string $S$ representing the text that Little L needs to read, and exactly two short strings $s_1$, $s_2$ representing the strings that Little L does not want to see. All three strings consist of lowercase letters. Little L strongly dislikes having both of these strings appear in the text as subsequences at the same time. He defines the discomfort value of a string $T$ as: the product of the number of occurrences of $s_1$ as a subsequence of $T$ and the number of occurrences of $s_2$ as a subsequence of $T$. Since he will read every substring of $S$, you now need to compute the sum of the discomfort values of all substrings of $S$. Since the answer may be too large, you only need to output the result modulo $998244353$. A string $H$ is a substring of $T$ if and only if $H$ can be obtained by deleting some characters from the beginning of $T$ and some characters from the end of $T$ (you may delete zero characters from the prefix/suffix, or delete the entire string to obtain the empty string). A string $H$ is a subsequence of $T$ if and only if $H$ can be obtained by deleting some characters from $T$ (you may delete zero characters, or delete all characters to obtain the empty subsequence).

The input consists of three lines, each containing a string of lowercase letters. The first line is $S$, the second line is $s_1$, and the third line is $s_2$. Here, $1\le |S|\le 1\times 10^5$, $1\le |s_1|,|s_2|\le 20$.

Output a single integer representing the computed answer.

| Substring start position | Substring end position | icpc count | ccpc count | | :----------: | :----------: | :----------: | :----------: | | 1 | 5 | 2 | 1 | | 1 | 6 | 2 | 1 | | 1 | 7 | 4 | 2 | | 1 | 8 | 4 | 2 | | 1 | 9 | 11 | 9 | | 2 | 5 | 0 | 1 | | 2 | 6 | 0 | 1 | | 2 | 7 | 0 | 2 | | 2 | 8 | 0 | 2 | | 2 | 9 | 1 | 9 | | 3 | 9 | 1 | 3 | | 4 | 9 | 1 | 1 | | 5 | 9 | 1 | 1 | | 6 | 9 | 1 | 0 | In all other substrings, the numbers of occurrences of the two strings as subsequences are both $0$. The answer is $(2\times 1) \times 2 + (4\times 2) \times 2 + 11\times 9 + (0\times 1)\times 2 + (0\times 2)\times 2 + 1\times 9 + 1\times 3 + (1\times 1)\times 2 + 1\times 0=133$. Translated by ChatGPT 5