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