HDU 2292

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[][],n,m,dp[] ;

ll cal(int s)

{

    ll temp=s- ;

    ll cnt= ;

    ll ans= ;

    while(temp-cnt>)

    {

        ans+=cnt/ ;

        temp-=cnt ;

        cnt*= ;

    }

    if(temp>=cnt/)ans+=cnt/ ;

    else ans+=temp ;

    return ans ;

}

int main()

{

    int t ;

    scanf("%d",&t) ;

    while(t--)

    {

        scanf("%I64d%I64d",&n,&m) ;

        memset(c,,sizeof(c)) ;

        for(int i= ;i< ;i++)

        {

            c[i][]=c[i][i]= ;

            for(int j= ;j<i ;j++)

                c[i][j]=(c[i-][j-]+c[i-][j])%m ;

        }

        memset(dp,,sizeof(dp)) ;

        dp[]=dp[]= ;

        for(int i= ;i<=n ;i++)

        {

            ll a=cal(i) ;

            ll b=i--a ;

            dp[i]=c[i-][a]*dp[a]%m*dp[b]%m ;

        }

        printf("%I64d\n",dp[n]%m) ;

    }

    return  ;

}

巴特西

HDU 2292

最新文章

热门文章