CF1679E Typical Party in Dorm

今天是宿舍的节日——Oleh 到来了，为了庆祝，女生们送给了他一个字符串。Oleh 非常喜欢这个礼物，于是立刻想出了一个问题并让你这个最好的朋友来解决。 给定一个长度为 $n$ 的字符串 $s$，该字符串由前 $17$ 个小写拉丁字母（即 $\{a, b, c, \ldots, p, q\}$）和问号组成。还有 $q$ 个询问。每个询问给定一个由前 $17$ 个小写拉丁字母中两两不同的字母组成的集合，可以用来替换字符串 $s$ 中的问号。 对于每个询问，要求计算：将字符串 $s$ 中的问号用可用字符集中的字母替换后，所有可能得到的字符串中，不同的回文子串的数量之和。答案需要对 $998\,244\,353$ 取模。 注意！当子串的起始和结束位置不同，即使内容相同，也被认为是不同的子串。因此，对于字符串 aba，不同的回文子串有 $4$ 个：a、b、a、aba。 来看几个用字母替换问号的例子。例如，字符串 aba??ee，在询问 $\{a, b\}$ 时，可以得到 ababaee 或 abaaaee，但不能得到 pizza、abaee、abacaba、aba?fee、aba47ee 或 abatree。 回文串是指从左到右和从右到左读都相同的字符串。

第一行包含一个整数 $n$（$1 \le n \le 1\,000$），表示字符串 $s$ 的长度。 第二行包含字符串 $s$，由 $n$ 个小写拉丁字母和问号组成。保证所有字母都属于集合 $\{a, b, c, \ldots, p, q\}$。 第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问的数量。 接下来 $q$ 行，每行一个字符串 $t$，表示可以用来替换问号的字符集合（$1 \le |t| \le 17$）。保证所有字母都属于集合 $\{a, b, c, \ldots, p, q\}$，且在集合中最多出现一次。

对于每个询问，输出一个整数，表示将字符串 $s$ 中的问号用可用字符集中的字母替换后，所有可能得到的字符串中不同回文子串的数量之和，对 $998\,244\,353$ 取模。

以第一个样例和第一个询问为例。我们只能得到一个字符串 abaaaba。它包含以下回文子串： 1. a —— 子串 $[1; 1]$。 2. b —— 子串 $[2; 2]$。 3. a —— 子串 $[3; 3]$。 4. a —— 子串 $[4; 4]$。 5. a —— 子串 $[5; 5]$。 6. b —— 子串 $[6; 6]$。 7. a —— 子串 $[7; 7]$。 8. aa —— 子串 $[3; 4]$。 9. aa —— 子串 $[4; 5]$。 10. aba —— 子串 $[1; 3]$。 11. aaa —— 子串 $[3; 5]$。 12. aba —— 子串 $[5; 7]$。 13. baaab —— 子串 $[2; 6]$。 14. abaaaba —— 子串 $[1; 7]$。 在第三个询问中，我们可以得到 4 个字符串：abaaaba、abababa、abbaaba、abbbaba。 由 ChatGPT 4.1 翻译