Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб | |
Максимальный балл: | 100 |
2-3 дерево - элегантная структура данных, изобретенная Джоном Хопкрофтом. Она предназначена для использования с той же целью, что и двоичное дерево поиска. 2-3 дерево представляет собой дерево с корнем, которое обладает следующими свойствами:
Единственное исключение - это когда дерево содержит ровно одну вершину. В этом случае корень дерева является и листом, и поэтому не имеет детей. Основная суть приведенных свойств в том, что дерево с l листьями имеет высоту O(logl).
Вообще говоря, может существовать несколько 2-3 деревьев с l листьями. Например, на следующем рисунке показаны два возможных дерева с 6 листьями.
По заданному числу l найдите количество различных 2-3 деревьев с l листьями. Так как ответ может быть довольно большим, выведите его по модулю r.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|