Description

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质: 每一个节点的度是0或2。度是这个节点的孩子的数目。 树的高度等于K(1 < K < 100)。高度是从根到任何叶子的最长的路径上的节点的数目; 叶子是指没有孩子的节点。 有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。

Input

第1行: 两个空格分开的整数, N和K。

Output

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

Sample Input

5 3

Sample Output

2

OUTPUT DETAILS:

有5个节点，高为3的两个不同的家谱：

层数	第一种	第二种
1	根节点	根节点
2	左节点数1右节点数1	左节点数1右节点数1
3	左节点数2右节点数1	左节点数1右节点数2

---

已知整个树的节点必定为$2n-1$（ 每一个母亲奶牛都生两小奶牛），去掉根节点就是$2n$，现在设整棵树共$n$个节点，由$x$个左子树构成，那么右子树个数就为$n-1-x$个，设$dp[i][j]$表示深度为$i$最多用$j$个点组成的二叉树的个数，则状态转移方程$dp[i][j]=dp[i][j]+dp[i-1][l]\ast dp[i-1][r]$，表示深度为$i$节点为$j$的树能由深度为$i-1$节点数之和为$j-1$的树组成（在两颗树的根节点上再加一个根节点连接深度就$+1$了） 其中$l$,$r$为左右子树个数，满足$r+l=n-1$且$l$和$r$一定为奇数（二叉树性质）。

---

AC代码

我这里用2个一维数组滚动求的值，因为对于深度为$x$的树只需要知道深度为$x-1$的所有情况即可，最后相减便是答案，需要注意的是相减求模得先加要模的值，防止相减为负数的这种情况

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define _mem(a,b) memset(a,0,(b+3)<<2)using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int inf = 0x3f;const double EPS = 1e-7;const double Pi = acos(-1);const int MOD = 9901;const int maxn = 2*1e2+9;int dp[maxn];int res[maxn];int main() { int a,b; cin >> a >> b; res[1] = 1; ///这里res为第一层，dp数组是从第二层开始的所以循环-1 for(int i=1;i<=b-1;i++){ _mem(dp,a); ///dp数组初始化为0 dp[1] = 1; for(int j=3;j<=a;j+=2) for(int k=1;k<=j-2;k+=2) dp[j] = (dp[j]+res[k]*res[j-1-k])%MOD; ///递推式 if(i!=b-1) memcpy(res,dp,(a+3)<<2); ///滚动，数组拷贝 } cout << (dp[a]-res[a]+MOD)%MOD << endl; return 0;}