#P5030. 奶牛家谱 Cow Pedigrees

    ID: 1215 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划其他构造竞赛USACO2.3树形结构前缀和

奶牛家谱 Cow Pedigrees

题目描述

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N{N}个节点(3<=N<200){(3 <= N < 200)}。这些二叉树有如下性质:

每一个节点的度是0{0}2{2}。度是这个节点的孩子的数目。

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

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

输入格式

1{1}行: 两个空格分开的整数, N{N}K{K}

输出格式

1{1} 行: 一个整数,表示可能的家谱树的个数除以9901{9901}的余数。

样例

输入样例

5 3

输出样例

2

提示

对于 100%{100\% }的数据,3n<200{3≤n<200}2k<100{2≤k<100}

5 5个节点,高为3 3的两个不同的家谱:

           @                                @
          / \                              / \
         @   @        和                  @   @
        / \                                  / \
       @   @                                @   @