Cow Pedigrees

Cow Pedigrees

Silviu Ganceanu -- 2003

Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

  • The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
  • The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

PROGRAM NAME: nocows

INPUT FORMAT

  • Line 1: Two space-separated integers, N and K.

SAMPLE INPUT (file nocows.in)

5 3

OUTPUT FORMAT

  • Line 1: One single integer number representing the number of possible pedigrees MODULO 9901.

SAMPLE OUTPUT (file nocows.out) 

2

OUTPUT DETAILS

Two possible pedigrees have 5 nodes and height equal to 3: 
           @                   @
/ \                 / \
@   @      and      @   @
/ \                     / \
@   @                   @   @

题意：
给出一颗二叉树的节点数n和高度m。计算满足n和m的二叉树数个数。
ans = (n, m) - (n, m - 1);
节点数为n高度小于等于m的数个数减去节点数为n高度小于等于m-1的数个数。
因为(n, m)里含有高度小于m的数个数，那些是不符合题意要求的,题意要求的数高度一定得是m。

代码入下：


/*
LANG: C
TASK: nocows
*/
#include<stdio.h>
int v[210][110];
void Set(int n, int m)
{
    int i, j;
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= m; j++)
        {
            v[i][j] = -1;
        }
    }
}
int Deal(int num, int dep)//求出高度小于或等于dep的情况数,//这个对(7，4)-(7，3)就清楚了。(7, 4)里有一个事高度为3的情况 
{
    int i, sum = 0;
    if (dep == 0)//如果高度是0，不存在情况。所以情况数为0 
    {
        return 0;
    }
    if (num == 1)//如果只有一个节点。不管高度多少，允许的情况就是一个节点的高度只为1.情况数为1 
    {
        return 1;
    }
    if (v[num][dep] != -1)//表示该情况没被计算过。 
    {
        return v[num][dep];
    }
    //计算左右子数组合的情况数，节点数为偶数时，情况数是0。只需要计算奇数情况 
    for (i = 1; i < num - 1; i += 2) 
    {
        //由于左右字数节点数不同，所以Deal(i, dep - 1)和Deal(num - 1 - i, dep - 1)不存在相同的结构 
        //所以要计算 Deal(i, dep - 1)*Deal(num - 1 - i, dep - 1) 和 Deal(num - 1 - i, dep - 1)*Deal(i, dep - 1)
        //当i = num - 1 - i ，只计算了一次。 
        sum = (sum + Deal(i, dep - 1) * Deal(num - 1 - i, dep - 1)) % 9901;
    }
    v[num][dep] = sum;//保存节点数为num，高度小于等于dep的情况数
    return sum;
}
int main()
{
    freopen("nocows.in", "r", stdin);
    freopen("nocows.out", "w", stdout);
    int t, n, m;
    scanf("%d%d", &n, &m);
    Set(n, m);
    t = (9901 + Deal(n, m) - Deal(n, m - 1)) % 9901;//求高度恰好为m的情况数 
    printf("%d\n", t);
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}