Good Bye 2022: 2023 is NEAR |
---|
Закончено |
У Чию есть скобочная последовательность$$$^\dagger$$$ $$$s$$$ длины $$$n$$$. Пусть $$$k$$$ равно минимальному числу символов, которое Чию должна удалить из $$$s$$$, чтобы сделать $$$s$$$ правильной$$$^\ddagger$$$.
Теперь Косия хочет, чтобы вы посчитали количество способов удалить $$$k$$$ символов из $$$s$$$ так, чтобы $$$s$$$ стала правильной, по модулю $$$998\,244\,353$$$.
Обратите внимание, что два способа удалить символы считаются различными, если и только если множества удаленных индексов различаются.
$$$^\dagger$$$ Скобочной последовательностью называется строка, состоящая только из символов «(» и «)».
$$$^\ddagger$$$ Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавляя только символы + и 1. Например, последовательности (())(), (), (()(())) и пустая строка являются правильными, а )(, (() и (()))( — нет.
Первая строка содержит строку $$$s$$$ ($$$1 \leq |s| \leq 5 \cdot {10}^5$$$) — скобочную последовательность.
Гарантируется, что $$$s$$$ содержит только символы «(» и «)».
Выведите одно целое число — количество способов удалить $$$k$$$ символов из $$$s$$$ так, чтобы $$$s$$$ стала правильной, по модулю $$$998\,244\,353$$$.
())(()
4
(
1
В первом примере можно показать, что минимальное количество символов, которое нужно удалить, равно $$$2$$$. Есть $$$4$$$ способа удалить $$$2$$$ символа так, чтобы $$$s$$$ стала правильной, как показано ниже. Удаленные символы показаны красным.
Во втором примере единственный способ сделать $$$s$$$ сбалансированной — удалить единственную скобку, чтобы получить пустую скобочную последовательность, которая считается сбалансированной.
Название |
---|