hdu 2292 Minimum Heap

ダイナミックプランニングのテーマは、ルートノードの左の子の中のノードの総数で構成できる組合せ総数*右の子の中のノードの総数で構成できる組合せ総数を使って、この木の総括点数から1人の子のノードの組合せ数を選択すればいいだけです.これで本題はやりやすくなり、再帰関数を書いて解決することができます.
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2292

#include <iostream>
using namespace std;

const int maxn=1005;
__int64 n,m;
__int64 cnt[maxn];
int c[maxn][maxn];

int son(int n)//          
{
    int t = 1;
    while (t <= n) t=t<<1|1;
    t = (t - 1) / 2;
    t = (t - 1) / 2;
    int sum = n - 1 - t;
    if (sum > 2 * t + 1)
	{
        sum = 2 * t + 1;
    }
    return sum;
}

void calc_c() {//      
    for (int i = 0; i < maxn; i++) 
    {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) 
        {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
        }
    }
}

__int64 slove(int n)// n            
{
    if(cnt[n])
        return cnt[n];
    if(n==0||n==1)
        return 1;
    int left=son(n);
    int right=(n-1)-left;
    return cnt[n]=( (slove(left)*slove(right) )%m )*(__int64)c[n-1][left]%m;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(cnt,0,sizeof(cnt));
        scanf("%I64d%I64d",&n,&m);
        calc_c();
        __int64 ans=slove(n);
        printf("%I64d
",ans);
    }
    return 0;
}