/*
ID:
LANG: C++
TASK: nocows
*/
#include <cstdio>
#include <cstdlib>
#define maxN 200
#define maxH 100
int main(){
FILE *fin = fopen("nocows.in", "r");
FILE *fout = fopen("nocows.out", "w");
int N, H; //节点个数，树的高度
fscanf(fin, "%d %d", &N, &H);
int varient[maxN][maxH] = {0}; //varient[n][h]是n个节点h高度的树的个数
varient[1][1] = 1;
varient[3][2] = 1;
int h, n, nlow = 3, nhi = 3, left, right;
for(h = 3; h <= H; h ++){ //高度为h
nlow += 2;
// nhi = nhi * 2 + 1; //这里到n = 32会溢出哦，不过早在2^n-1超过N就已经不起作用了
if(h < 20) nhi = nhi * 2 + 1;
for(n = nlow; n <= nhi && n <= N; n += 2){ //节点数n
for(left = 1; left < n - 1; left += 2){ //左子树的节点数
right = n - 1 - left;
if(varient[left][h - 1]){ //左子树高度为h-1, 右=[1,h-1]
for(int rh = 1; rh <= h - 1; rh ++)
if(varient[right][rh])
varient[n][h] += varient[left][h - 1] * varient[right][rh];
varient[n][h] %= 9901; //等全部加完又溢出了
}
if(varient[right][h - 1]){ //右子树高度为h-1, 左=[1,h-1)
for(int lh = 1; lh < h - 1; lh ++)
if(varient[left][lh])
varient[n][h] += varient[left][lh] * varient[right][h - 1];
varient[n][h] %= 9901;
}
}
varient[n][h] %= 9901;
}
}
// for(int i = 1; i < H; i ++){
// fprintf(fout, "\nh = %d--------------------------------------------\n", i);
// for(int j = 1; j < N; j ++){
// fprintf(fout, "%d\t", varient[j][i]);
// }
// }
fprintf(fout, "%d\n", varient[N][H]);
return 0;
}
Test 1: TEST OK [0.000 secs, 4176 KB]
Test 2: TEST OK [0.000 secs, 4176 KB]
Test 3: TEST OK [0.000 secs, 4176 KB]
Test 4: TEST OK [0.000 secs, 4176 KB]
Test 5: TEST OK [0.000 secs, 4176 KB]
Test 6: TEST OK [0.000 secs, 4176 KB]
Test 7: TEST OK [0.000 secs, 4176 KB]
Test 8: TEST OK [0.000 secs, 4176 KB]
Test 9: TEST OK [0.014 secs, 4176 KB]
Test 10: TEST OK [0.014 secs, 4176 KB]
Test 11: TEST OK [0.014 secs, 4176 KB]
Test 12: TEST OK [0.014 secs, 4176 KB]
dp
经点拨才有思路。二叉树这么漂亮的递归结构，想想也是很容易用前面已经计算过的结论的。然后就迷在到底怎么用了，越想越复杂，后来发现考虑第一个分叉，分成左右两个子树，较大的那个高度是h-1，每个子树的节点数也小于n，就足以使用前面算的结果了。
溢出
第一次遇到数字极大，结果要取模的问题。print一下发现很快就遍布着负数，果然溢出。试着用long long int 也不够。嗯果然是不打算让我算准确数值的。有一个很常用的结论(a % n) * (b % n) == (a * b) % n，所以每一个值都取下模就好了。
于是又挂了，print一下发现我加完再取模又就已经溢出了，那就每加一次就取模吧。
又一个测试挂了，发现前面的nhi，节点数的上界，在高度为32的时候溢出了，又一个果然……不过这个上界早就没用了，溢出之前停掉好了。
最后
本来以为后面数大了需要剪枝，结果不需要就已经这么快了，那就算了……
本来也是N * H ^ 2的复杂度，没多大。我这里好像是N * H ^ 3，因为比官答的累加复杂了点，把rh和lh过了一遍，不过数字小，还是很快……
