Decorating a Christmas Tree
Time limit1sMemory limit512 MB
Count binary trees with exactly L levels and N distinct nodes, ordered by level and by a preorder placement rule, modulo 100030001.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Tree, Combinatorics, Math
- Solved
- No attempts yet
Problem
Around Christmas, Hanyang University decorates a tree in front of the Aegi Gate. This year, Kim Hanyang is in charge of decorating the Christmas tree. But Kim Hanyang is a binary-tree fool who knows nothing about trees except binary trees. So Kim Hanyang wants to decorate the tree for the Aegi Gate in the shape of a binary tree.
Hanyang University provides Kim Hanyang with only 'tree balls' as decorations. The number of balls is limited, and the height of the tree to be decorated is fixed. When the university limits the height of the tree, Kim Hanyang must make a tree of exactly that height. The tree cannot be shorter or taller than that height, and only the number of balls the university allows may be used. Also, all of the provided 'tree balls' must be used.
Given the limit on the number of balls and the tree height, Kim Hanyang wonders how many ways he can decorate the tree. Let us Hanyang students help Kim Hanyang, who knows nothing but binary trees!
For example, if the number of balls is 5 and the tree height is 3, the number of ways to decorate the tree is as follows.
Input
The first line gives the number of balls N and the tree height L in order. (1 ≤ N ≤ 300, 1 ≤ L ≤ 300)
Output
Print the number of ways to decorate the tree modulo 100,030,001.
Hint
A binary tree is a tree data structure in which each node has at most two child nodes, a left child and a right child. With 1 node at the top, then 2 below it, and so on, the d-th row from the top can have 2d−1 nodes.