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

Solution

$f[i][j]$表示树大小为$i$，最深深度小于等于$j$的二叉树数量。

$f[i][j]=\sum_{k=1}^{i}f[k-1][j-1]*f[i-k][j-1]$

多组数据用记搜

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N (609) 5 #define MOD (1000000007) 6 using namespace std; 7  8 int T,n,h,f[N][N],ans; 9 10 int DP(int sz,int hi)11 {12     if (sz==0) return 1;13     if (hi==0) return sz==1;14     if (f[sz][hi]!=-1) return f[sz][hi];15     f[sz][hi]=0;16     for (int i=1; i<=sz; ++i)17         (f[sz][hi]+=1ll*DP(i-1,hi-1)*DP(sz-i,hi-1)%MOD)%=MOD;18     return f[sz][hi];19 }20 21 int main()22 {23     memset(f,-1,sizeof(f));24     scanf("%d",&T);25     while (T--)26     {27         scanf("%d%d",&n,&h);28         ans=DP(n,h);29         if (h>0) ans-=DP(n,h-1);30         printf("%d\n",(ans%MOD+MOD)%MOD);31     }32 }