4.奶牛家谱树(cowtree)
问题描述
学校开展社会实践活动,小John随老师和同学们一道来到了奶牛场。奶牛场经理听了小John的故事,说他这里也有一个问题需要解决,想请小John帮忙,小John拍着胸脯说,“没问题,交给我吧!请您告诉我问题”,经理告诉小John:奶牛场准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示,这些二叉树总共有 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