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