问题1471--奶牛家谱树-2014

1471: 奶牛家谱树-2014

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

卡卡西帮助原木加工厂工人解决难题之后,发现已过去2 个小时,由于太专心,没注意到
老师已经带着其他小朋友去了下一站——奶牛场。卡卡西在指示箭头的帮助下,加速赶路,很
快来到了奶牛场,终于看见了大家,并告诉大家加工厂的问题解决啦,大家都很佩服卡卡西乐
于助人的精神。奶牛场经理听了卡卡西的故事,说他这里也有一个问题需要解决,想请卡卡西
帮忙,卡卡西拍着胸脯说, “没问题,交给我吧!请您告诉我问题”,经理告诉卡卡西:奶牛
场准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间
的关系可以用二叉树来表示,这些二叉树总共有N 个节点(3≤N < 200),并具有如下性质: 
(1)每一个节点的度只能是0 或2。度是这个节点的孩子的数目; 
(2)树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子节点所需要经过的节点数(包
括根节点和最远的叶子节点);叶子节点是指没有孩子的节点。 
如果一个家谱的树结构不同于另一个的,那么这两个家谱就是不同的。请问,有多少种不
同的家谱树结构?输出可能的家谱树的个数除以9901 的余数。

输入

共一行,两个正整数N和K(中间用空格隔开),分别表示
二叉树的节点总数和二叉树的高度。

输出

共一行。一个正整数,表示可能的家谱树的个数除以9901 的
余数。

样例输入

5 3

样例输出

2

提示

输出结果表示在5 个节点,高为3 的情况下,有两个不同的家谱树,除以9901 
的余数为2。家谱树结构如下: 

其中:家谱树1中共5个节点,树的高度为3,A为根节点,C、D、E为叶子节点(没有孩子节点),
A、B节点的度均为2;家谱树2中共5个节点,树的高度为3,A为根节点,B、D、E为叶子节点(没
有孩子节点),A、C节点的度均为2。 
 数据范围: 
3≤N < 200, 1 < K < 100


来源/分类


[提交] [状态]