Олимпиадный тренинг

Задача . E. Типичная вечеринка в общаге


Задача

Темы: битмаски дп Комбинаторика Строки *2400

Сегодня в общаге праздник  — приехал Олег, в честь чего девочки подарили ему строку. Олегу очень понравился подарок, поэтому он тут же придумал и предложил вам, лучшему его другу, следующую задачу.

Вам дана строка \(s\) длины \(n\), которая состоит из первых \(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.


Примеры
№Входные данныеВыходные данные
1 7
ab??aba
8
a
b
ab
abc
abcd
abcde
abcdef
abcdefg 
14
13
55
105
171
253
351
465
2 11
???????????
6
abcdefghijklmnopq
ecpnkhbmlidgfjao
olehfan
codef
glhf
q 
900057460
712815817
839861037
756843750
70840320
66

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет