eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

АВЛ-деревья

АВЛ-деревья

АВЛ-дерево --- сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на \textbf{1}. АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса. Для фиксированного количества вершин может существовать несколько АВЛ-деревьев. Например, существует шесть АВЛ-деревьев, состоящих из пяти вершин. \includegraphics{https://static.e-olymp.com/content/e9/e9b2f0f45aede1674ff4fd2aca6c4fbb7affc96d.jpg} Также деревья с одинаковым количеством вершин могут иметь различную высоту. Например, существуют деревья из семи вершин с высотами \textbf{2} и \textbf{3} соответственно. \includegraphics{https://static.e-olymp.com/content/3e/3eb13f6f7830dd7beeb072f0a29aeb21a49336d7.jpg} Требуется по заданным \textbf{n} и \textbf{h} найти количество АВЛ-деревьев, состоящих из \textbf{n} вершин и имеющих высоту \textbf{h}. Так как ответ может быть очень большим, требуется найти остаток от деления искомого количества на \textbf{786433}. \InputFile Во входном файле даны числа \textbf{n} и \textbf{h} (\textbf{1} ≤ \textbf{n} ≤ \textbf{65535}, \textbf{0} ≤ \textbf{h} ≤ \textbf{15}). \OutputFile Выведите одно число --- остаток от деления количества АВЛ-деревьев, состоящих из \textbf{n} вершин и имеющих высоту \textbf{h}, на \textbf{786433}.
Лимит времени 5 секунд
Лимит использования памяти 256 MiB
Входные данные #1
7 3
Выходные данные #1
16

Объяснение: 786433 - простое число, 786433 = 3*2^18 + 1

Автор Дмитрий Жуков
Источник Зимняя Школа, Харьков 2011, День 2