题目详情题解（0）讨论（0）提交记录（0）

CF1679E.Typical Party in Dorm

提高+/省选-

通过率：0%

时间限制：2.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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 ss of length nn, which consists of the first 1717 lowercase Latin letters {aa, bb, cc, …\ldots, pp, qq} and question marks. And qq queries. Each query is defined by a set of pairwise distinct lowercase first 1717 letters of the Latin alphabet, which can be used to replace the question marks in the string ss.

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 ss by replacing question marks with available characters. The answer must be calculated modulo 998 244 353998\,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 44: a, b, a, aba.

Consider examples of replacing question marks with letters. For example, from the string aba??ee when querying {aa, bb} 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.

今天是宿舍楼的假日——奥列赫到访，为此女生们送给他一根字符串。奥列赫非常喜欢这份礼物，于是立刻构思出一道题目，并向他最好的朋友（也就是你）提出。

给定一个长度为 nn 的字符串 ss，该字符串仅由前 1717 个小写拉丁字母 {a,b,c,…,p,q}\{a, b, c, \ldots, p, q\} 和问号组成；另有 qq 个查询。每个查询由一个互不相同的、属于前 1717 个小写拉丁字母的字符集合定义，该集合中的字符可用于替换字符串 ss 中的问号。

查询的答案为：对所有将 ss 中问号替换成所允许字符后所能得到的字符串，分别计算其回文子串的不同数量，再将这些数量求和。结果需对 998 244 353998\,244\,353 取模。

请注意！当两个子串在原字符串中的起始位置与结束位置不同时，即视为不同的子串。因此，字符串 aba 的不同回文子串数量为 44：a、b、a、aba。

下面给出问号替换的示例：例如，对字符串 aba??ee 和查询集合 {a,b}\{a, b\}，可得到字符串 ababaee 或 abaaaee，但不能得到 pizza、abaee、abacaba、aba?fee、aba47ee 或 abatree 等字符串。

回顾定义：回文串是指正读与反读均完全相同的字符串。

输入格式

The first line contains a single integer nn (1≤n≤1 0001 \le n \le 1\,000) — the length of the string ss.

The second line contains the string ss, which consists of nn lowercase Latin letters and question marks. It is guaranteed that all letters in the string belong to the set {aa, bb, cc, …\ldots, pp, qq}.

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

This is followed by qq lines, each containing a single line tt — a set of characters that can replace question marks (1≤∣t∣≤171 \le |t| \le 17). It is guaranteed that all letters in the string belong to the set {aa, bb, cc, …\ldots, pp, qq} and occur at most once.

第一行包含一个整数 nn（1≤n≤1 0001 \le n \le 1\,000）—— 字符串 ss 的长度。

第二行包含字符串 ss，该字符串由 nn 个小写拉丁字母和问号组成。保证字符串中所有字母均属于集合 {aa, bb, cc, …\ldots, pp, qq}。

第三行包含一个整数 qq（1≤q≤2⋅1051 \le q \le 2 \cdot 10^5）—— 查询次数。

接下来是 qq 行，每行包含一个字符串 tt —— 可用于替换问号的字符集合（1≤∣t∣≤171 \le |t| \le 17）。保证字符串 tt 中所有字母均属于集合 {aa, bb, cc, …\ldots, pp, qq}，且每个字母至多出现一次。

输出格式

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

对于每个查询，输出一个数字——所有能从字符串 ss 得到的字符串中回文子串的总数，对 998 244 353998\,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

说明/提示

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 [11; 11].
  2. b — substring [22; 22].
  3. a — substring [33; 33].
  4. a — substring [44; 44].
  5. a — substring [55; 55].
  6. b — substring [66; 66].
  7. a — substring [77; 77].
  8. aa — substring [33; 44].
  9. aa — substring [44; 55].
  10. aba — substring [11; 33].
  11. aaa — substring [33; 55].
  12. aba — substring [55; 77].
  13. baaab — substring [22; 66].
  14. abaaaba — substring [11; 77].

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

考虑第一个样例及其第一个查询。我们仅能通过替换问号得到一个字符串——abaaaba。该字符串包含以下回文子串：

  1. a — 子串 [11; 11]。
  2. b — 子串 [22; 22]。
  3. a — 子串 [33; 33]。
  4. a — 子串 [44; 44]。
  5. a — 子串 [55; 55]。
  6. b — 子串 [66; 66]。
  7. a — 子串 [77; 77]。
  8. aa — 子串 [33; 44]。
  9. aa — 子串 [44; 55]。
  10. aba — 子串 [11; 33]。
  11. aaa — 子串 [33; 55]。
  12. aba — 子串 [55; 77]。
  13. baaab — 子串 [22; 66]。
  14. abaaaba — 子串 [11; 77]。

在第三次查询中，我们得到 4 行：abaaaba、abababa、abbaaba、abbbaba。

输入解题思路，AI测评打分。不知道怎么写?

首页