【bzoj3769】spoj 8549 BST again

2014年12月3日1,4520

Description

求有多少棵大小为n的深度为h的二叉树。(树根深度为0;左右子树有别;答案对1000000007取模)

Input

第一行一个整数T,表示数据组数。
以下T行,每行2个整数n和h。

Output

共T行,每行一个整数表示答案(对1000000007取模)

Sample Input

2
2 1
3 2

Sample Output

2
4

HINT

对于100%的数据,1<=n<=600,0<=h<=600,1<=T<=10

题解

f[i][j]表示大小i,深度小于j的二叉树数量

f[i][j]=(1<=k<=i)Σf[k-1][j-1]*f[i-k][j-1]

。。。理论上好像是n^3