P6695 Google Meme Translator (Enhanced Version)

This problem is provided by @[wolfind](https://www.luogu.com.cn/user/104593). [Original link](https://www.luogu.com.cn/problem/P6693) (note that the original problem and the enhanced version differ **only** in the **formula in** `interpretation method`, the **modulus**, and the **Constraints**).

**Note: For convenience, in the following, all strings are 1-indexed, i.e. positions start from $1$.** Xiao L treats the original text before each meme-making and the result after meme-making as two strings $A$ and $B$, both consisting **only of lowercase letters**. We define a “split sequence” and “split substring” as follows: - For a string of length $n$, a “split sequence” is defined as: there exists a sequence $p$ of length $k+2$ such that $0=p_0

The first line contains three positive integers $n,m,t$. The next line contains a string of length $n$, representing string $A$. The next line contains a string of length $m$, representing string $B$.

One line containing one integer, the answer modulo $998244353$.

For Sample 1, there are the following interpretation methods: + $p=\{0,4\},q=\{0,5\}$, meme level is $25$. + $p=\{0,1,4\},q=\{0,2,5\}$, meme level is $9$. + $p=\{0,2,4\},q=\{0,1,5\}$, meme level is $11$. + $p=\{0,2,4\},q=\{0,4,5\}$, meme level is $11$. + $p=\{0,3,4\},q=\{0,3,5\}$, meme level is $9$. + $p=\{0,1,2,4\},q=\{0,2,4,5\}$, meme level is $3$. + $p=\{0,1,3,4\},q=\{0,2,3,5\}$, meme level is $3$. + $p=\{0,2,3,4\},q=\{0,1,3,5\}$, meme level is $3$. The total meme level is $74$. ### Constraints “This problem uses bundled subtasks.” - Subtask 1 ( $20\%$ ): $n,m\leq 50,t\leq 2$. - Subtask 2 ( $30\%$ ): $n,m\leq 200,t\leq 2$. - Subtask 3 ( $20\%$ ): $t\leq 10$. - Subtask 4 ( $30\%$ ): no special restrictions. For $100\%$ of the testdata, $n,m\leq 1000,t\leq 1000000$, and $A$ and $B$ **contain only lowercase letters**. Translated by ChatGPT 5