Вы наконец добрались до сокровища! Конечно же это строка $$$s$$$ длины $$$n=2^k$$$, состоящая из скобок.
Скажем прямо — кот Персик$$$\text{}^\dagger$$$ обожает скобочные последовательности и степени двойки!
Персик играет со строкой $$$s$$$ — несколько раз (возможно, ноль) делит её на части и собирает обратно.
За один шаг происходит следующее:
Последовательность делится на блоки длины $$$m = 2^x$$$ $$$(x \ge 1)$$$, каждый блок делится на две половины, половины внутри блока меняются местами.
Пример:
$$$x = 2, m = 4, s = (()) \Rightarrow |((\cdot))| \Rightarrow |))\cdot((| \Rightarrow ))(($$$
$$$x = 2, m = 4, s = ((()))() \Rightarrow |((\cdot()|))\cdot()| \Rightarrow |()\cdot((|()\cdot))| \Rightarrow ()((()))$$$
$$$x = 1, m = 2, s = ((()))() \Rightarrow |(\cdot(|(\cdot)|)\cdot)|(\cdot)| \Rightarrow |(\cdot(|)\cdot(|)\cdot)|)\cdot(| \Rightarrow (()()))($$$
Нам интересно, когда Персик наиграется (то есть ему надоест менять исходную строку) — для этого помогите нам узнать (в зависимости от типа запроса):
- Сколько существует различных вариантов получить правильную скобочную последовательность$$$^\ddagger$$$ (ПСП) из исходной строки $$$s$$$, пока Персик с ней играет. Два варианта считаются различными, если для некоторого $$$i$$$ символ, стоящий изначально на позиции $$$i$$$ переместился на разные позиции в этих двух вариантах.
- Сколько существует различных ПСП, которые можно получить из исходной строки. Две ПСП $$$a, b$$$ считаются различными, если существует индекс $$$i$$$ такой, что $$$a_i \ne b_i$$$.
$$$^\dagger \text{}$$$ Персик — акула в мире программирования.
$$$^\ddagger$$$ Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавляя только символы $$$+$$$ и $$$1$$$. Например, последовательности $$$(())(), (), (()(()))$$$ и пустая строка являются правильными, а $$$)(, (()$$$ и $$$(()))($$$ — нет.
В первой строке вводится одно число $$$T$$$ — количество тестовых примеров $$$(1 \le T \le 10\,000)$$$.
Во второй строке вводится одно число $$$Q$$$ — тип запроса (общий для всех тестовых примеров) $$$(1 \le Q \le 2)$$$.
В следующих $$$T$$$ строках вводится по одной скобочной последовательности. $$$(2 \le |s_i| \le 2^{22})$$$.
Суммарная длина всех вводимых последовательностей не превосходит $$$2^{22}$$$ $$$(\sum_{i = 1}^T |s_i| \le 2^{22})$$$.
Для каждой строки выведите требуемое число:
При $$$Q = 1$$$ — количество различных перестановок, т.ч. итоговая строка ПСП.
При $$$Q = 2$$$ — количество различных ПСП, которые можно получить такими действиями.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы |
| 1 | 18 | $$$q = 1$$$, $$$\sum_{i = 1}^T |s_i| \le 2^8$$$ | – |
| 2 | 26 | $$$q = 1$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{14}$$$ | 1 |
| 3 | 26 | $$$q = 1$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{22}$$$ | 1, 2 |
| 4 | 13 | $$$q = 2$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{12}$$$ | – |
| 5 | 17 | $$$q = 2$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{17}$$$ | 4 |
21))((((()))()
2 2
22))((((()))()
1 2
Если взять строку $$$s = (^1(^2)^3)^4$$$ (после символа указана его изначальная позиция), то она сама является ПСП, а также после одного шага при $$$x = 1, m = 2$$$ получим строку $$$(^2(^1)^4)^3$$$. Итого есть два варианта.
На иллюстрации изображено применение одного шага $$$x = 2, m = 4$$$ к строке $$$((()))()$$$.
Иллюстрация к примеру
