#2155. [2014 安徽省] 奶牛家谱树(cowtree)

    ID: 2155 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划树结构2014安徽省小学组

[2014 安徽省] 奶牛家谱树(cowtree)

题目描述

    卡卡西帮助原木加工厂工人解决难题之后,发现已过去 22 个小时,由于太专心,没注意到老师已经带着其他小朋友去了下一站——奶牛场。卡卡西在指示箭头的帮助下,加速赶路,很快来到了奶牛场,终于看见了大家,并告诉大家加工厂的问题解决啦,大家都很佩服卡卡西乐于助人的精神。奶牛场经理听了卡卡西的故事,说他这里也有一个问题需要解决,想请卡卡西帮忙,卡卡西拍着胸脯说,“没问题,交给我吧!请您告诉我问题”,经理告诉卡卡西:奶牛场准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示,这些二叉树总共有 NN 个节点(3N<2003≤N < 200),并具有如下性质:

    (1)每一个节点的度只能是 0022。度是这个节点的孩子的数目;

    (2)树的高度等于 K(1<K<100)K(1 < K < 100)。高度是从根到最远的那个叶子节点所需要经过的节点数(包括根节点和最远的叶子节点);叶子节点是指没有孩子的节点。

    如果一个家谱的树结构不同于另一个的,那么这两个家谱就是不同的。请问,有多少种不同的家谱树结构?输出可能的家谱树的个数除以 99019901 的余数。

输入格式

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

输出格式

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

样例

输入#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。

数据范围

3N<200,1<K<1003≤N < 200, 1 < K < 100