#2155. [2014 安徽省] 奶牛家谱树(cowtree)
[2014 安徽省] 奶牛家谱树(cowtree)
题目描述
卡卡西帮助原木加工厂工人解决难题之后,发现已过去 个小时,由于太专心,没注意到老师已经带着其他小朋友去了下一站——奶牛场。卡卡西在指示箭头的帮助下,加速赶路,很快来到了奶牛场,终于看见了大家,并告诉大家加工厂的问题解决啦,大家都很佩服卡卡西乐于助人的精神。奶牛场经理听了卡卡西的故事,说他这里也有一个问题需要解决,想请卡卡西帮忙,卡卡西拍着胸脯说,“没问题,交给我吧!请您告诉我问题”,经理告诉卡卡西:奶牛场准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示,这些二叉树总共有 个节点(),并具有如下性质:
(1)每一个节点的度只能是 或 。度是这个节点的孩子的数目;
(2)树的高度等于 。高度是从根到最远的那个叶子节点所需要经过的节点数(包括根节点和最远的叶子节点);叶子节点是指没有孩子的节点。
如果一个家谱的树结构不同于另一个的,那么这两个家谱就是不同的。请问,有多少种不同的家谱树结构?输出可能的家谱树的个数除以 的余数。
输入格式
共一行,两个正整数 和 (中间用空格隔开),分别表示二叉树的节点总数和二叉树的高度。
输出格式
共一行。一个正整数,表示可能的家谱树的个数除以 的余数。
样例
输入#1
5 3
输出#1
2
解释#1
输出结果表示在 5 个节点,高为 3 的情况下,有两个不同的家谱树,除以 9901 的余数为 2。家谱树结构如下:
其中:家谱树 1 中共 5 个节点,树的高度为 3,A 为根节点,C、D、E 为叶子节点(没有孩子节点),A、B节点的度均为2;家谱树2中共5个节点,树的高度为3,A 为根节点,B、D、E 为叶子节点(没有孩子节点),A、C 节点的度均为 2。
数据范围