Автор: | Жюри зимних сборов 2009 | Ограничение времени: | 5 сек | |
Входной файл: | btrees.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | btrees.out | |||
Максимальный балл: | 100 |
Если б дерево умело говорить...
Б-дерево — структура для хранения данных во вторичной памяти (например, на жёстком диске). Б-дерево обладает несколькими свойствами:
Обратите внимание, что корень может являться листом.
Два Б-дерева считаются различными, если они различны как графы с помеченными вершинами, или если вершина с одинаковыми пометками содержит различное количество ключей. Например, существует всего 8 различных Б-деревьев с четырьмя ключами и со степенью ветвления 2 (см. рисунок).
Посчитайте количество различных Б-деревьев с n ключами в листьях и степенью ветвления t.
В первой строке находятся два натуральных числа n и t — количество ключей в листьях и степень ветвления, соответственно (1 ≤ n ≤ 500, 2 ≤ t ≤ 109).
В первой строке выведите единственное число без ведущих нулей — количество Б-деревьев с n ключами в листьях и степенью ветвления t.
№ | Входной файл (btrees.in ) |
Выходной файл (btrees.out ) |
---|---|---|
1 |
|
|
2 |
|
|