174
правки
Изменения
Нет описания правки
Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из $d[2n - i - 1][{\rm ndepth}]$. Теперь посчитаем, как изменится ответ из-за наличия $k$ типов скобок. У нас имеется $2n - i - 1$ неопределённых позиций, из которых $\rm ndepth$ являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет $(2n - i - 1 - {\rm ndepth}) / 2$ пар) могут быть любого из $k$ типов, поэтому ответ умножается на эту степень числа $k$.
===Получение $k$-й последовательности===
Здесь пусть $n$ — количество пар скобок в последовательности. В данной задаче по заданному $k$ требуется найти $k$-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
Как и в предыдущем разделе, посчитаем '''динамику''' $d[i][j]$ — количество правильных скобочных последовательностей длины $i$ с балансом $j$.
Пусть сначала допустимы только скобки '''одного''' типа.
Будем двигаться по символам искомой строки, с $0$-го по $2n - 1$-ый. Как и в предыдущей задаче, будем хранить счётчик $\rm depth$ — текущую глубину вложенности в скобки. В каждой текущей позиции будем перебирать возможный символ - открывающую скобку или закрывающую. Пусть мы хотим поставить сюда открывающую скобку, тогда мы должны посмотреть на значение $d[i + 1][\rm depth + 1]$. Если оно $\ge k$, то мы ставим в текущую позицию открывающую скобку, увеличиваем $\rm depth$ на единицу и переходим к следующему символу. Иначе мы отнимаем от $k$ величину $d[i + 1][\rm depth + 1]$, ставим закрывающую скобку и уменьшаем значение $\rm depth$. В конце концов мы и получим искомую скобочную последовательность.
Пусть теперь разрешён не один, а '''$k$ типов''' скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение $d[i + 1][\rm ndepth]$ на величину $k^{(2n - i - 1 - \rm ndepth) / 2}$, чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только $2n - i - 1 - \rm ndepth$, поскольку $\rm ndepth$ скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).
== Источники ==
