BST again
Time Limit: 10 Sec Memory Limit: 256 MB[][][]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
1<=n<=600,0<=h<=600,1<=T<=10
Solution
我们运用DP来求解。
记f[i][j]表示点数为i，深度==j的方案数；
记g[i][j]表示点数为i，深度<=j的方案数。转移的时候所以枚举一个点k作为根，那么左边显然就有k-1个点，右边就有i-k个点。
此时深度恰好为j-1的方案数为：
g[k-1][j-1] * g[i-k][j-1] - g[k-1][j-2] * g[i-k][j-2]。所以我们就可以得到答案了。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 1005;12 const int MOD = 1e9 + 7;13 14 int T;15 int n, h;16 int x, y;17 int f[ONE][ONE], g[ONE][ONE];18 19 struct pwoer20 {21 int x, y;22 }a[ONE];23 24 int get()25 {26 int res=1,Q=1; char c;27 while( (c=getchar())<48 || c>57)28 if(c=='-')Q=-1;29 if(Q) res=c-48; 30 while((c=getchar())>=48 && c<=57) 31 res=res*10+c-48;32 return res*Q; 33 }34 35 void Modit(int &a)36 {37 if(a < 0) a += MOD;38 if(a >= MOD) a -= MOD;39 }40 41 int main()42 {43 T = get();44 for(int i = 1; i <= T; i++)45 a[i].x = get(), a[i].y = get() + 1,46 n = max(n, a[i].x), h = max(h, a[i].y);47 48 f[0][0] = 1; for(int i = 0; i <= h; i++) g[0][i] = 1;49 f[1][1] = 1; for(int i = 1; i <= h; i++) g[1][i] = 1;50 for(int i = 2; i <= n; i++)51 {52 for(int j = 2; j <= i; j++)53 for(int k = 1; k <= i; k++)54 Modit(f[i][j] += (s64)g[k - 1][j - 1] * g[i - k][j - 1] % MOD - (s64)g[k - 1][j - 2] * g[i - k][j - 2] % MOD);55 56 g[i][0] = f[i][0];57 for(int j = 1; j <= h; j++)58 Modit(g[i][j] = g[i][j - 1] + f[i][j]);59 } m60 61 for(int i = 1; i <= T; i++)62 printf("%d\n", f[a[i].x][a[i].y]);63 64 }