Counting Full Binary Trees
Time limit2sMemory limit128 MB
Count full binary trees with exactly n nodes and height exactly k, modulo 9901, using a height-bounded DP and subtraction trick.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Tree, Combinatorics, Math
- Solved
- No attempts yet
Problem
Count how many different binary trees satisfy all of the following conditions.
- The tree has exactly n nodes. (1 <= n < 200)
- Every node has degree 0 or 2. The degree of a node is the number of children it has.
- The height of the tree is exactly k. (1 < k < 100) The height is the number of nodes on the longest path from the root to a leaf. A leaf is a node with no children.
Because the tree is binary, changing the placement of left and right children can make a different tree.
The answer can be very large, so compute it modulo 9901.
Input
The first line contains two integers n and k.
Output
Output the number of different binary trees satisfying the conditions, modulo 9901.