Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

hdu 2292 Minimum Heap

#include <iostream>
using namespace std;

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

int cal(int n)
{
    
int t = 1;
    
while (t <= n) t = t * 2 + 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)
{
    
if(F[n])
        
return F[n];
    
if(n==0||n==1)
        
return 1;
    
int left=cal(n);
    
int right=(n-1)-left;
    
return F[n]=( (slove(left)*slove(right) )%m )*(__int64)c[n-1][left]%m;
}

int main()
{
    
int T;
    scanf(
"%d",&T);
    
while(T--)
    
{
        memset(F,
0,sizeof(F));
        scanf(
"%I64d%I64d",&n,&m);
        calc_c();
        __int64 ans
=slove(n);
        printf(
"%I64d\n",ans);
    }

    
return 0;
}

posted on 2009-10-05 11:19 Drolca 阅读(274) 评论(1)  编辑 收藏 引用

评论

# re: hdu 2292 Minimum Heap   回复  更多评论   

请教一下楼主,求左孩子个数的时候是什么思路啊?
2011-08-26 08:57 | IAccepted

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理