首页 > 代码库 > HDU 2292

HDU 2292

2024-07-03 07:55:07   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=2292

题意：1-n个节点，题目给出了完全二叉树的定义（这个定义似乎有歧义，此题以题目描述为准），且要保持最小堆性质（根节点小于左右子树内的任意元素），问有多少种不同组合

解法：dp，dp[n]表示n个元素的合法排列数量。一共n个节点，左子树有a个节点，则右子树有n-1-a个节点，dp[n]=C(n-1,a)*dp[a]*dp[n-1-a]，其中a可以轻易算出。

公式解释：除去根节点，在剩下的n-1个元素中取a个，这a个元素的合法排列有dp[a]种，剩下n-1-a个节点的合法排列有dp[n-1-a]种。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
typedef __int64 ll ;
ll c[1005][1005],n,m,dp[1005] ;
ll cal(int s)
{
    ll temp=s-1 ;
    ll cnt=2 ;
    ll ans=0 ;
    while(temp-cnt>0)
    {
        ans+=cnt/2 ;
        temp-=cnt ;
        cnt*=2 ;
    }
    if(temp>=cnt/2)ans+=cnt/2 ;
    else ans+=temp ;
    return ans ;
}
int main()
{
    int t ;
    scanf("%d",&t) ;
    while(t--)
    {
        scanf("%I64d%I64d",&n,&m) ;
        memset(c,0,sizeof(c)) ;
        for(int i=1 ;i<1001 ;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 ;
        }
        memset(dp,0,sizeof(dp)) ;
        dp[0]=dp[1]=1 ;
        for(int i=2 ;i<=n ;i++)
        {
            ll a=cal(i) ;
            ll b=i-1-a ;
            dp[i]=c[i-1][a]*dp[a]%m*dp[b]%m ;
        }
        printf("%I64d\n",dp[n]%m) ;
    }
    return 0 ;
}
View Code

 


联系
我们