← 返回题目列表

Codeforces · 1679/E

E. 宿舍里的典型聚会

中文机器翻译题面 查看原题

今天是宿舍的假期 — Oleh 来了,为了纪念,女孩们送给了他一根绳子。 Oleh 非常喜欢这个礼物,所以他立即想出了一个办法,向你,他最好的朋友,提出了以下问题。

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,它由前 $$$17$$$ 小写拉丁字母 {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} 和问号组成。和 $$$q$$$ 查询。每个查询由一组成对不同的拉丁字母表前 $$$17$$$ 字母定义,可用于替换字符串 $$$s$$$ 中的问号。

查询的答案是通过用可用字符替换问号可以从原始字符串 $$$s$$$ 获得的所有字符串中作为回文的不同子字符串的数量之和。答案必须以 $$$998\,244\,353$$$ 为模计算。

注意!当两个子字符串在字符串中的起始位置和结束位置不同时,它们就不同。因此,作为字符串 aba 的回文的不同子字符串的数量将为 $$$4$$$:a, b, a, aba。

考虑用字母替换问号的示例。例如,当查询 {$$$a$$$, $$$b$$$} 时,从字符串 aba??ee 中,您可以获取字符串 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$$$ 为模。

示例

输入 #1

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

输出 #1

14
13
55
105
171
253
351
465

输入 #2

11
???????????
6
abcdefghijklmnopq
ecpnkhbmlidgfjao
olehfan
codef
glhf
q

输出 #2

900057460
712815817
839861037
756843750
70840320
66

注意

考虑第一个示例和其中的第一个查询。替换问号后,我们只能得到一个字符串——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。