hdu 4359 dp

 1 /*
 2 题目大意：给n个节点的二叉树第i个节点的权值为2^(i-1)，
 3 求所有含左右子树的节点都符合左子树的权和小于右子树权和的种数。
 4 */
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <cstring>
 8 using namespace std;
 9 
10 typedef __int64 LL;
11 const int maxn=365;
12 const int mod=1e9+7;
13 LL c[maxn][maxn];
14 LL dp[maxn][maxn];//i个节点,深度不超过j的子数个数
15 
16 void getcombinations()
17 {
18     memset(c,0,sizeof(c));c[0][0]=1;
19     for(int i=1;i<maxn;i++)
20     {
21         c[i][0]=1;
22         for(int j=1;j<=i;j++)
23             c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
24     }
25 }
26 
27 void init()
28 {
29     getcombinations();
30     int i,j,k;
31     for(i=1;i<maxn;i++) dp[1][i]=1;
32     for(i=2;i<maxn;i++)
33     {
34         for(j=1;j<maxn;j++)
35         {
36             dp[i][j]=i*dp[i-1][j-1]*2%mod;//i个点选一个出来做根,只有一颗子树，可以放左也可以右
37             for(k=1;k<=i-2;k++)
38                 /*
39                 根据等比数列求和公式2^0+2^1+......+2^(n-1)=2^n-1  <  2^n
40                 i个节点有两个子树,选1个出来做根有i种,把剩余节点中权最大的给右子树
41                 ,那么就是i-2个点选k个点做左子树,剩下的都做右子树。
42                 (c(i,1)*c(1,1)*c(i-2,k)*c(i-2-k,i-2-k)*dp(k,j-1)*dp(i-1-k,j-1))
43                 */
44                 dp[i][j]=(dp[i][j]+i*c[i-2][k]%mod*dp[k][j-1]%mod*dp[i-1-k][j-1]%mod)%mod;
45         }
46     }
47 }
48 int main()
49 {
50     init();
51     int t,icase=0,n,d;
52     scanf("%d",&t);
53     while(t--)
54     {
55         scanf("%d %d",&n,&d);
56         printf("Case #%d: %I64d
",++icase,(mod+dp[n][d]-dp[n][d-1])%mod);
57     }
58     return 0;
59 }