HDU 4359 Easy tree DP? -- 我只能说是个dp

/*
	HDU 4359 Easy tree DP?
	题意：求任意节点下左子树最大值小于右子树最大值的二叉树方案数
	
	我只能说这是一个dp（rt）

	状态：i个节点在满足不大于j深度有 dp[i][j] 种方案数
	初始化：
	        CLR(dp,0)
	        dp[1][1~360] = 1  各种深度仅一个节点方案数为1
	转移：
	（1）i个中挑一个为root 并且该root仅有左子树（or右子树,so ×2）
		dp[i][j] += dp[i-1][j-1]*nCr(i,i-1)*2 
	（2）i个中挑一个为root 并且该root有左子树(假设拥有k个节点)and右子树
		dp[i][j] += 
		nCr(i-2,k) *	    从i-2(因为去掉了一个root和一个必须放在右子树的最大节点)个中挑k个的方案数
		dp[k][j-1] *	    从i-2个中挑出的k个作为root的左子树的方案数   （因为没算root那一层所以j-1）
		dp[i-1-k][j-1] *    上面挑剩下的i-1-k个节点构成{深度<=j-1}的方案数 （因为没算root那一层所以j-1）
		nCr(i,i-1)	    从i个中挑1个为root的方案数

*/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <ctime>
#include <queue>
#include <cmath>
#include <set>
#define CLR(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long       ll;
typedef pair<int,int>   pii;

const int N   = 360 + 10;
const ll  MOD = 1e9 + 7;
int n,d;
ll C[N][N]={0};
ll dp[N][N]={0}; // i个节点在满足不大于j深度有 dp[i][j] 种方案数

ll nCr(ll n,ll r){
	if(C[n][r]!=-1)return C[n][r];
	if(n==r)return 1;
	if(n<r)return 0;
	if(r==1)return n;
	return C[n][r] = (nCr(n-1,r-1) + nCr(n-1,r))%MOD;
}

void pre(){
	CLR(C,-1);
	int n_p = 360;
	int depth = 360;
	// 初始化各种深度,0个点方案数为1,1个点方案数也为1
	for(int j = 1 ; j <= depth ; j++)
		dp[1][j] = 1;

	for(int i = 2 ; i <= n_p ; i++){
		for(int j = 1 ; j <= depth ; j++){
			dp[i][j] = nCr(i,1)*dp[i-1][j-1]%MOD *2%MOD;
			if(dp[i][j] >= MOD)	dp[i][j] %= MOD;
			for(int k = 1 ; k <= i-2 ; k++){ 
				// 虽然选取一个做为root，但是剩余中最大的应该在最右叶子上，因此去掉两个点
				// 保证root左子树不为空，因此 k >= 1
				// k表示 root左子树上有k个点
				//            左k个点   右i-1-k个点        左挑k个        root的挑法
				dp[i][j] += dp[k][j-1] * dp[i-1-k][j-1]%MOD * nCr(i-2,k)%MOD * nCr(i,1) % MOD;
				if(dp[i][j] >= MOD)	dp[i][j] %= MOD;
			}
		}
	}
}

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("Output.txt","w",stdout);
	pre();
	int T,ca=0;cin >> T;
	while(T--){
		scanf("%d%d",&n,&d);
		printf("Case #%d: %I64d\n",++ca, (dp[n][d] - dp[n][d-1] + MOD)%MOD);
	}
	return 0;
}