P17236 ‘STA - R10’ Painting Walls and Walls Painting

Alice is a rabbit who likes symmetry. Now she appoints you to help paint a wall.  There is a wall now, and string $a$ represents the color at each position. The desired result is represented by string $b$. The character set is lowercase letters. You may perform any number of operations. Each time, choose a sub-interval of $a$ with length $L$ and a string $c$ with length $L$, and assign that interval to be $c$. For efficiency reasons, the $L$ you choose must satisfy $L \ge 3$. For symmetry reasons, the string you choose must be an odd-length palindrome. If you can finish this task, you will get a reward of $220$ “feilin” (pinyin: 菲林)! Alice has fixed the colors of some positions, and marks the unfixed ones with `?`. You want to know how many possible values of $b$ allow you to get the reward. Alice reminds you that this number is too large, so you decide to take it modulo $998244353$.

Formal statement: The character set is lowercase letters. Given strings $a, b$ of length $n$, define one operation as choosing a sub-interval $[l, r]$ of $a$ whose length is odd and $\ge 3$, and assigning it to be a palindrome string. If $a$ can be transformed into $b$ through a finite number of operations, then $a$ is called “good”. Now you are given $a$ and a string $b$ consisting of lowercase letters and `?` (note that the number of `?` can be any integer in $[0, n]$). If each `?` in $b$ can be replaced by any lowercase letter, how many possible assignments make $a$ “good”? Output the answer modulo $998244353$.

The first line contains a positive integer $n$, the length of the strings. The second line contains a string $a$ of length $n$, consisting only of lowercase letters. The third line contains a string $b$ of length $n$, consisting of lowercase letters and `?`.

Output one integer, the number of valid assignments modulo $998244353$.

**This problem uses bundled testdata**. ::cute-table{tuack} | Subtask | $n\le$ | Special Property | Score | |:-:|:-:|:-:|:-:| | $1$ | $5$ | None | $10$ | | $2$ | $10^5$ | $b$ contains only lowercase letters | $10$ | | $3$ | $10^5$ | $b$ contains only `?` | $20$ | | $4$ | $2 \times 10^3$ | None | $20$ | | $5$ | $10^6$ | None | $40$ | Translated by ChatGPT 5