Typical Party in Dorm
Contest: Codeforces Round 791 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, combinatorics, dp, strings

Today is a holiday in the residence hall — Oleh arrived, in honor of which the girls gave him a string. Oleh liked the gift a lot, so he immediately thought up and offered you, his best friend, the following problem.

You are given a string $$$s$$$ of length $$$n$$$, which consists of the first $$$17$$$ lowercase Latin letters {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} and question marks. And $$$q$$$ queries. Each query is defined by a set of pairwise distinct lowercase first $$$17$$$ letters of the Latin alphabet, which can be used to replace the question marks in the string $$$s$$$.

The answer to the query is the sum of the number of distinct substrings that are palindromes over all strings that can be obtained from the original string $$$s$$$ by replacing question marks with available characters. The answer must be calculated modulo $$$998\,244\,353$$$.

Pay attention! Two substrings are different when their start and end positions in the string are different. So, the number of different substrings that are palindromes for the string aba will be $$$4$$$: a, b, a, aba.

Consider examples of replacing question marks with letters. For example, from the string aba??ee when querying {$$$a$$$, $$$b$$$} you can get the strings ababaee or abaaaee but you cannot get the strings pizza,  abaee, abacaba, aba?fee, aba47ee, or abatree.

Recall that a palindrome is a string that reads the same from left to right as from right to left.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1\,000$$$) — the length of the string $$$s$$$.

The second line contains the string $$$s$$$, which consists of $$$n$$$ lowercase Latin letters and question marks. It is guaranteed that all letters in the string belong to the set {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$}.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

This is followed by $$$q$$$ lines, each containing a single line $$$t$$$ — a set of characters that can replace question marks ($$$1 \le |t| \le 17$$$). It is guaranteed that all letters in the string belong to the set {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} and occur at most once.

Output format:
For each query print one number — the total numbers of palindromic substrings in all strings that can be obtained from the string $$$s$$$, modulo $$$998\,244\,353$$$.

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

Note:
Consider the first example and the first query in it. We can get only one string as a result of replacing the question marks  — abaaaba. It has the following palindrome substrings:

1. a  — substring [$$$1$$$; $$$1$$$].
2. b  — substring [$$$2$$$; $$$2$$$].
3. a  — substring [$$$3$$$; $$$3$$$].
4. a  — substring [$$$4$$$; $$$4$$$].
5. a  — substring [$$$5$$$; $$$5$$$].
6. b  — substring [$$$6$$$; $$$6$$$].
7. a  — substring [$$$7$$$; $$$7$$$].
8. aa  — substring [$$$3$$$; $$$4$$$].
9. aa  — substring [$$$4$$$; $$$5$$$].
10. aba  — substring [$$$1$$$; $$$3$$$].
11. aaa  — substring [$$$3$$$; $$$5$$$].
12. aba  — substring [$$$5$$$; $$$7$$$].
13. baaab  — substring [$$$2$$$; $$$6$$$].
14. abaaaba  — substring [$$$1$$$; $$$7$$$].

In the third request, we get 4 lines: abaaaba, abababa, abbaaba, abbbaba.

Example input:
7
ab??aba
8
a
b
ab
abc
abcd
abcde
abcdef
abcdefg

Example output:
14
13
55
105
171
253
351
465

Example input:
11
???????????
6
abcdefghijklmnopq
ecpnkhbmlidgfjao
olehfan
codef
glhf
q

Example output:
900057460
712815817
839861037
756843750
70840320
66

Editorial:
We are given a string $$$s$$$, we need to count the number of palindromes in all possible versions of it if the characters "$$$?$$$" can be replaced by some letters of the English alphabet, which are set by queries.
Let us solve the problem initially for a $$$1$$$ query.
First, we can see that instead of counting the number of palindromes in each possible version of string $$$s$$$, we can count the number of strings in which a substring $$$[l;r]$$$ would be a palindrome.
Consider the substring $$$[l;r]$$$. Suppose the set of allowed characters in this query is $$$Q$$$. What would be the effect of the substring on the answer? Divide the characters of the substring into pairs: first with last, second with penultimate, and so on. If the length of the substring is odd, pair the central character with itself. Now let's consider each pair separately:
• If two characters of the pair are equal and they are not question marks, then this pair does not affect the answer.
• If two characters of the pair are equal and they are question marks, then this pair multiplies the answer by $$$|Q|$$$, where $$$|Q|$$$  — the number of possible characters to replace in this query. (Let's call the number of such pairs $$$f$$$).
• If two characters of the pair are not equal and there is no question mark among them, then this substring will never be a palindrome.
• If two characters of a pair are not equal and there is a question mark among them, you must check if the letter that is not a question mark belongs to the set $$$Q$$$, if not, then in this query this substring will never be a palindrome.
Thus, to get the answer for the substring $$$[l;r]$$$ it is enough:
• Check for blocking pairs  — if they exist, the answer is $$$0$$$ by definition.
• Otherwise, the answer is $$$|Q|^{d+f}$$$, where $$$d$$$ and $$$f$$$ are defined above.
Let's assign to each possible set of letters a binary mask of size $$$\alpha$$$, where $$$\alpha$$$  — the size of the alphabet in the problem. In the future, we will assume that mask and set are the same.
Consider possible blocking pairs of some substring $$$[l;r]$$$, they are of two kinds:
1. If two characters of the pair are not equal and there is no question mark among them, then this substring will never be a palindrome and we do not consider it.
2. If two characters of the pair are not equal and there is a question mark between them, a character that is not a question mark must be in the query for us to consider this substring.
Next, let us note the following fact: $$$d+f$$$ does not depend on the query $$$Q$$$, because $$$d$$$ depends only on $$$l$$$ and $$$r$$$, and $$$f$$$  — on the number of pairs where both characters are question marks.
It follows that every substring of the form $$$[l;r]$$$:
• Or is simply ignored if it has a blocking pair of the first type. (These substrings will not be mentioned further in the tutorial  — when we say substrings, we automatically mean the one described below).
• Either is characterized by a pair of numbers ($$$P$$$; $$$d+f$$$).
Consider an arbitrary query $$$Q$$$, how to calculate the answer for it? We need to go through all substrings, check whether $$$P \subseteq Q$$$ and if so, add $$$|Q|^{d+f}$$$ to the answer.
The values of $$$P$$$ and $$$d+f$$$ for the substring $$$[l;r]$$$ can be found quickly by knowing the same values for the substring $$$[l+1;r-1]$$$. Thus, by iterating over the parity of the palindrome length, then its center, and then its length itself, we can quickly find these values for all the substrings.
Thus, our solution has asymptotics so far $$$O$$$($$$n^2$$$ $$$+$$$ $$$q \cdot n^2$$$), which is obviously too slow.
But first, let's figure out how to solve the problem if we have $$$|Q|$$$  — fixed? Let's create an array of size $$$2^\alpha$$$ (let's call it $$$R$$$). For each substring, let's add to $$$R_P$$$ value $$$|Q|^{d+f}$$$. What does this give us? We will then have in $$$R_i$$$ the sum of answers from all the substrings $$$P$$$ of which is equal to $$$i$$$. To find the answer in this case we have to sum all $$$R_i$$$ where $$$i \subseteq Q$$$.
Actually, we have reached the asymptotics $$$O$$$($$$n^2$$$ $$$+$$$ $$$q \cdot 2^\alpha$$$) or $$$O$$$($$$n^2$$$ $$$+$$$ $$$3^\alpha$$$).
But! The problem of finding the sum of subset values is a well-known one and solves our subproblem for $$$O$$$($$$\alpha$$$ $$$\cdot$$$ $$$2^\alpha$$$). In more detail: https://codeforces.com/blog/entry/45223
Well, here we have reached the asymptotics of $$$O$$$($$$n^2$$$ $$$+$$$ $$$\alpha \cdot 2^\alpha$$$), which is enough.
Let us return to the original problem. First, note that we don't have many different $$$|Q|$$$  — just $$$\alpha$$$. So we create $$$\alpha$$$ different arrays of size $$$2^\alpha$$$. When processing the current substring, we add $$$i^{d+f}$$$ to each of the $$$\alpha$$$ arrays at position $$$P$$$, where $$$i$$$  — the index of the current array. Thus, it is as if we $$$\alpha$$$ times solved the problem for a fixed $$$|Q|$$$. We need to take the sum over subsets of $$$Q$$$ from the $$$|Q|$$$th array to get the answer.
The final asymptotic of the solution  — $$$O$$$($$$\alpha \cdot n^2$$$ $$$+$$$ $$$\alpha^2 \cdot 2^\alpha$$$).
Applied optimizations in the author's solution:
• Power optimization: we will often need different values of numbers from $$$1$$$ to $$$\alpha$$$ in powers from $$$0$$$ to $$$n$$$, so to remove $$$log$$$ from the asymptotic, a precalculation of these values is used. This optimization is necessary to guarantee a full score on the problem.
• Addition optimization: we do not need to add a subset ($$$P$$$; $$$d+f$$$) to arrays whose index is less than $$$|P|$$$. This is since they will not affect the answer in any way. (Since the sets from which the answer will be taken in this array have fewer elements than $$$P$$$, they cannot, by definition, be $$$P$$$ supersets.) This optimization is unlikely to have much effect on runtime. It is written here for a clearer understanding of the author's solution.
• Modulo optimization: The take modulo operation is slower than other operations, so it is worth avoiding. Here we often use the sum modulo of two numbers that do not exceed $$$998\,244\,353$$$, so we will replace it by using (a+b >= M ? a+b-M : a+b) instead of (a+b)%M