Pro.ID21266 TitleTree Count Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21266 AC1 Submit1 Ratio100.00% 时间&空间限制描述Our superhero Carry Adder has uncovered the secret method that the evil Head Crash uses to generate the entrance code to his fortress in Oakland. The code is always the number of distinct binary search trees with some number of nodes, that have a specific property. To keep this code short, he only uses the least significant nine digits.
The property is that, for each node, the height of the right subtree of that node is within one of the height of the left subtree of that node. Here, the height of a subtree is the length of the longest path from the root of that subtree to any leaf of that subtree. A subtree with a single node has a height of 0, and by convention, a subtree containing no nodes is considered to have a height of −1.
输入Input will be formatted as follows. Each test case will occur on its own line. Each line will contain only a single integer, N, the number of nodes. The value of N will be between 1 and 1427, inclusive. 输出Description Our superhero Carry Adder has uncovered the secret method that the evil Head Crash uses to generate the entrance code to his fortress in Oakland. The code is always the number of distinct binary search trees with some number of nodes, that have a specific property. To keep this code short, he only uses the least significant nine digits.
The property is that, for each node, the height of the right subtree of that node is within one of the height of the left subtree of that node. Here, the height of a subtree is the length of the longest path from the root of that subtree to any leaf of that subtree. A subtree with a single node has a height of 0, and by convention, a subtree containing no nodes is considered to have a height of −1.
Input Input will be formatted as follows. Each test case will occur on its own line. Each line will contain only a single integer, N, the number of nodes. The value of N will be between 1 and 1427, inclusive. Output Your output is one line per test case, containing only the nine-digit code (note that you must print leading zeros). Sample Input 1
3
6
21 Sample Output 000000001
000000001
000000004
000036900 Source 样例输入1
3
6
21 样例输出000000001
000000001
000000004
000036900 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-3-10 22:00 , Processed in 0.021136 second(s), 26 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
