农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:
每一个节点的度是0或2。度是这个节点的孩子的数目。
树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。
有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。
格式
PROGRAM NAME: nocows
INPUT FORMAT (file nocows.in)
第1行: 两个空格分开的整数, N和K。
OUTPUT FORMAT (file nocows.out)
第 1 行: 一个整数，表示可能的家谱树的个数除以9901的余数。
SAMPLE INPUT
5 3
SAMPLE OUTPUT
2
OUTPUT DETAILS
有5个节点，高为3的两个不同的家谱：
@ @
/ \ / \
@ @ 和 @ @
/ \ / \
@ @ @ @
分析：
（官方题解， 译 by 巨菜逆铭）
这是一个DP问题。我们所关心的树的性质是深度和节点数，所以我们可以做这样一张表：table[i][j]表示深度为i、节点数为j的树的个数。根据给定的约束条件，j必须为奇数。你如何构造一棵树呢？当然是由更小的树来构造了。一棵深度为i、节点数为j的树可以由两个子树以及一个根结点构造而成。当i、j已经选定时，我们选择左子树的节点数k。这样我们也就知道了右子树的节点数，即j-k-1。至于深度，至少要有一棵子树的深度为i-1才能使构造出的新树深度为i。有三种可能的情况：左子树深度为i-1 ，右子树深度小于i-1；右子树深度为i-1，左子树深度小于i-1；左右子树深度都为i-1。事实上，当我们在构造一棵深度为i的树时，我们只关心使用的子树深度是否为i-1或更小。因此，我们使用另一个数组smalltrees[i-2][j]记录所有深度小于i-1的树，而不仅仅是深度为i-2的树。知道了上面的这些，我们就可以用以下三种可能的方法来建树了：
table[i][j] += smalltrees[i-2][k]*table[i-1][j-1-k];
// 左子树深度小于i-1，右子树深度为i-1
table[i][j] += table[i-1][k]*smalltrees[i-2][j-1-k];
// 左子树深度为i-1，右子树深度小于i-1
table[i][j] += table[i-1][k]*table[i-1][j-1-k];
// 左右子树深度都为i-1
另外，如果左子树更小，我们可以对它进行两次计数，因为可以通过交换左右子树来得到不同的树。总运行时间为O(K*N^2)，且有不错的常数因子。（官方标程见源码-c部分）
首先明确一下题目的意思：用N个点组成一棵深度为K的二叉树，求一共有几种方法？设dp[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则：
dp[i,j]=∑(dp[k,j-1]×dp[i-1-k,j-1])(k∈{1..i-2})
边界条件：dp[1,i]=1
我们要求的是深度恰好为K的方法数S，易知S=dp[n,k]-dp[n,k-1]。但需要注意的是，如果每次都取模，最后可能会有dp[n,k]<dp[n,k-1],所以可以用S=(dp[n,k]-dp[n,k-1]+v) mod v 。
【参考程序】：
/*
ID: XIONGNA1
PROG: nocows
LANG: C++
*/
#include<iostream>
using namespace std;
long long f[201][101];
int n,m;
int main()
{
freopen("nocows.in","r",stdin);
freopen("nocows.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) f[1][i]=1;
for (int i=2;i<=n;i++)
for (int j=1;j<=m;j++)
{
f[i][j]=0;
for (int k=0;k<=i-1;k++)
{
f[i][j]+=f[k][j-1]*f[i-1-k][j-1];
f[i][j]%=9901;
}
}
f[n][m]=(f[n][m]-f[n][m-1]+9901)%9901;
printf("%lld\n",f[n][m]);
return 0;
}