HDU OJ -- Count the Trees

一、概述

1.问题描述

给定n个节点，问最多能构造出多少种“二元搜索树”。

二元搜索树是一种树形结构，由节点和边构成，对于每个节点，最多含有两条边。

2.问题链接

HDU OJ -- Count the Trees

3.问题截图

如图1.1所示。

图1.1  问题截图

二、算法思路

下面说明一些与算法描述相关的约定。

1）算法的描述涉及排列与组合的相关操作。

P[x,y]代表排列，表示从x中取出y个做排列有几种可能，如P[2,2]=2x1=2，排列有关于取出项目的顺序。

C[x,y]代表组合，表示从x中取出y个做组合有几种可能，如C[2,2]=2x1/2x1=1，组合则无关于顺序。

2）R(n)代表剩余节点的数目。

3）y(n)表示规模为n时，二元搜索树的数目，即最终的结果。

下面通过n取不同的值说明算法的思路。

1.当n=1时

当只有一个节点时，很明显，只能够造出1种含有根节点的二元搜索树。

见图2.1，图中由名为R(x)的节点和边组成的树称为解答树，用于描述算法进行的过程。

图2.1  n=1时的解答树

在图2.1中，初始状态有1个节点，用R(1)表示，此时需要选取节点作为根节点，这在解答树中用竖直的边表示。因为当前剩余1个节点，所以可以选择作为根节点的数目可以用P[1,1]表示。选取完根节点，由于当前剩余0个节点，所以用R(0)表示。此时n=1时可以构造的二元搜索树的数目就是边上的权值，y(1) = P[1,1] = 1。

（文中出现的“根节点”，皆表示实际的二元搜索树中的根节点，而不是解答树的根节点）

2.当n=2时

解答树见图2.2。

图2.2  n=2时的解答树

首先需要选取根节点，因为这里初始状态有2个节点，图中用R(2)表示，所以可以进行根节点的选择数目可以用P[2,1]表示。选择完根节点，此时剩余1个节点，在图中用R(1)表示。这是可以看见有一条从R(1)左边发出的边。这里约定，在解答树中，从某个节点左边发出的边代表从此节点构造单分支结构（由于在实际的二元搜索树中，并不是此解答树，每个节点可能具有0，1，2个分支，这里的单分支就代表了在二元搜索树的某个节点中构造1个分支的结构），图2.3用n=2时对应的实际的二元搜索树中阐述了这个约定。

图2.3  n=2时对应的实际二元搜索树

在图2.3中，实际二元搜索树的根节点就代表了解答树中的R(1)节点，因为此时已经完成了根节点的构造并只剩一个节点，这时解答树左边发出的边就对应为实际的二元搜索树中的根节点构造单分支的情形。

现在回到图2.2的解答树，在从R(2)构造完根节点到达R(1)时，此时剩余一个节点，所以只能构造单分支结构，而因为单分支在实际的二元搜索树中可以在左或者右，所以这里在R(1)到R(0)的边用x2表示。

因此在n=2时，最终的二元搜索树的数目就是各边的权值的乘积，因为边的权值表示了每一个节点当前可能做出的选择数目。

y(2)=P[2,1]xP[1,1]X2=2x1x2=4。

3.当n=3时

解答树如图2.4所示。

图2.4  n=3时的解答树

在构造完根节点到达R(2)时，此时剩余2个节点，这意味着当前不仅可以为根节点构造单分支结构，还可以构造双分支结构，在解答树中用从某个节点右边发出的边表示为实际的二元搜索树的某个节点构造双分支结构。在图2.5中用n=3时解答树对应的实际的二元搜索树说明了双分支结构。

图2.5  n=3时对应的实际二元搜索树

图2.5中，实际二元搜索树的根节点代表了解答树中的R(2)节点，此时R(2)右边发出的到R(0)的边代表了为实际的二元搜索树进行如图双分支结构的构造。

回到图2.4的解答树，在构造完根节点到达R(2)时，此时剩余2个节点，可以选择构造单分支或者双分支结构，故在R(2)有从左右发出的边。

首先，说明R(2)右边发出的边，即构造双分支结构，需要从剩下的节点中选取2个节点构造双分支结构，可以用P[2,2]表示选择的数目，用P[2,2]是因为节点出现在左右分支的顺序不同对应的二元搜索树不同。

再来看R(2)左边发出的边，即为R(2)代表的节点构造单分支结构，需要从剩下的节点中选取1个节点，用P[2,1]表示选择的数目，此时到达R(1)节点，此时对R(1)节点所处的情况进行分析：

R(1)表示了根节点R(2)向下进行了一次单分支扩展的情况，即此时实际的二元搜索树仅有一条分支，而此时还剩下1个节点等待被构造，这情况正好是n=2时中R(1)子树所反映的内容，如下图2.6中方框中内容所示。

图2.6  n=2时解答树中的R(1)子树

在方框中，n=2时解答树中的R(1)表示的情况为：根节点构造完后，还剩余1个节点等待被构造，此时的实际二元搜索树由于仅有根节点，所以也只有一条分支。所以我们可以将n=2时R(1)包含的构造数目，即“只有1条分支的情况下，还剩余1个节点，包含的可能构造数目”这个信息保存起来，以便用于n=3时的相同情景，这里将n=2时R(1)的子树包含的数目信息记为f(1)。

因此，y(3)=P[3,1] x (P[2,1]x2xf(1) + P[2,2])=3x(2x2x2 + 2)=30。

4.当n=4时

解答树如图2.7所示。

图2.7  n=4时的解答树

R(4)，R(3)情况不再赘述，现来看R(2)所处的情况，R(2)表示：此时只有1条分支，还有2个节点等待被构造，这与n=3时的R(2)的子树所示的情景相同，如图2.8中方框所示。

图2.8  n=3时解答树中的R(2)子树

在图中，即n=3时的解答树中，方框中的R(2)节点也处于相同的情景：此时有1个分支，还有2个节点等待被构造。可以得出结论：在此问题中，大规模的问题需要用到已求出的小规模问题的解答，因此可以将每个小规模的f(n)都保存起来以便后续的操作。

现在分析n=4时R(3)的右分支R(1)，此时R(1)可以简单的用f(1)来表示吗？

不可以！

因为f(1)表示：只有1个分支，还剩1个节点的情况下可能的构造数目，而此时的R(1)是由R(3)构造了双分支结构而得到的，这意味着此时具有2个分支，因此在这里需要单独对其进行分析。

当有2个分支，并且剩余1个节点，可能进行的子树构造为：

剩余的1个节点R(1)可能在实际二元搜索树的左，或者右分支进行构造。由于只可能在左、右分支的其中一个进行构造，此时的情况转变为：1个分支，1个节点的构造问题，即此时R(1)包含的可能子树构造数目为：f(1) x 2。

这里记g(m)为：有2个分支，剩余m个节点下包含的构造数目。所以g(1) = f(1) x 2。

因此n=4时，最终的结果y(4) = P[4,1] x (P[3,1] x 2 x f(2) + P[3,2] x g(1)) = 4 x (3 x 2 x 10 + 6 x 4) = 336。

5.当n=5时

解答树如图2.9所示。

图2.9  n=5时的解答树

R(5)，R(4)，R(3)的情形不再赘述，现分析R(4)的右分支R(2)。

R(2)所处的情况是：当前拥有2个分支，还有2个节点需要进行构造。如前述，此时不能用f(2)表示这种情况。那么这种情况下包含的可能构造数目为：

1）剩余的2个节点都在左、或者右分支进行构造。可能的构造数目为：f(2) x 2。

2）剩余的其中1个节点在左，另1个节点在右进行构造。可能的构造数目为：C[2,1] x f(1) x C[1,1] x f(1)。这里由于我们只需要从剩余节点中取出1个节点，不关心它的顺序，因此用组合的函数进行可能选择的计算。

这个计算公式的意思是：从剩余的2个节点中取出1个节点（C[2,1]），让这个取出的节点在双分支的左分支进行构造（C[2,1] x f(1)），再从剩余的1个节点中取出1个节点（C[1,1]），让其在双分支的右分支进行构造（C[1,1] x f(1)），由于这两部分的结果可以互相组合作为二元搜索树的结果，所以最后的结果为这两部分的乘积（C[2,1] x f(1) x C[1,1] x f(1)）。

将1），2）的和作为在情况“2个分支，剩余2个节点”下可能的构造数目，即g(2) = f(2) x 2 + C[2,1] x f(1) x C[1,1] x f(1)。

综上，最后的结果y(5) = P[5,1] x (P[4,1] x 2 x f(3) + P[4,2] x g(2)) = 5 x (4 x 2 x 84 + 12 x 28) = 5040。

6.当n>=6时

在之后的n中，如上所述，问题求解的关键在于计算“2个分支，剩余m个节点包含的可能构造数目”，即计算g(m)，(m>=1)。

前面已经计算了m=1，2时的值，下面再通过分析m=3，4时的结果总结g(m)的规律。

当m=3时，即当前有2个分支，剩余3个节点时，可能的构造如下所述。

1）3个节点均在双分支中的某一分支。可能的构造为：f(3) x 2

2）1个节点在左分支，2个节点在右分支。可能的构造为：C[3,1] x f(1) x C[2,2] x f(2)

3）2个节点在左分支，1个节点在右分支。可能的构造为：C[3,2] x f(2) x C[1,1] x f(1)

m=4时。

1）4个节点均在双分支中的某一分支。可能的构造为：f(4) x 2

2）1个节点在左分支，3个节点在右分支。可能的构造为：C[4,1] x f(1) x C[3,3] x f(3)

3）2个节点在左分支，2个节点在右分支。可能的构造为：C[4,2] x f(2) x C[2,2] x f(2)

4）3个节点在左分支，1个节点在右分支。可能的构造为：C[4,3] x f(3) x C[1,1] x f(1)

可以发现g(m)的计算具有一定的规律，总结为如下公式。

g(m) = f(m) x 2 + sum<i=1~m-1>(C[m,i] x f(i) x C[m-i,m-i] x f(m-i))。其中sum<...>(...)为求和公式，<...>为可能的取值。

综上所述，y(n) = {

                                n>=1    ,    P[n,1] x f(n-1)

                                }

f(m) = {

                m=0    ,    1

                m=1    ,    2

                m=2    ,    10

                m>=3    ,    P[m,1] x 2 x f(m-1) + P[m,2] x g(m-2)

            }

g(m) = {

                m>=1    ,    f(m) x 2 + sum<i=1~m-1>(C[m,i] x f(i) x C[m-i,m-i] x f(m-i))

            }

三、算法实现

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    class NumStr
    {
    public:
        string str;
        NumStr()=default;
        NumStr(string str):str(str){}
        bool operator==(NumStr& oprand)
        {
            if(str.size()!=oprand.str.size())
                return false;
            for(unsigned i=0;i<str.size();i++)
            {
                if(str[i]!=oprand.str[i])
                    return false;
            }
            return true;
        }
        bool operator<=(NumStr& oprand)
        {
            unsigned len1=str.size();
            unsigned len2=oprand.str.size();
            if(len1>len2)
                return false;
            else if(len1<len2)
                return true;
            for(int i=len1-1;i>=0;i--)
            {
                if(str[i]>oprand.str[i])
                    return false;
                else if (str[i]<oprand.str[i])
                    return true;
            }
            return true;
        }
        NumStr operator-(NumStr oprand)
        {
            //result always positive
            NumStr ret;
            unsigned len=oprand.str.size();
            bool borrow=false;
            char tmp;
            unsigned i;
            for(i=0;i<len;i++)
            {
                tmp='0'+str[i]-oprand.str[i]-borrow;
                if(tmp<'0')
                {
                    tmp+=10;
                    borrow=true;
                }
                else
                {
                    borrow=false;
                }
                ret.str+=tmp;
            }
            for(i=len;i<str.size();i++)
            {
                tmp=str[i]-borrow;
                if(tmp<'0')
                {
                    tmp+=10;
                    borrow=true;
                }
                else
                {
                    borrow=false;
                }
                ret.str+=tmp;
            }
            if(ret.str.back()=='0')
                ret.str.pop_back();
            return ret;
        }
        NumStr operator+(NumStr oprand)
        {
            NumStr ret;
            bool carry=0;
            unsigned minLen=str.size()<=oprand.str.size()?str.size():oprand.str.size();
            char tmp;
            for(unsigned i=0;i<minLen;i++)
            {
                tmp=str[i]+oprand.str[i]+carry-'0';
                if(tmp>'9')
                {
                    carry=1;
                    tmp-=10;
                }
                else
                {
                    carry=0;
                }
                ret.str+=tmp;
            }
            if(str.size()>minLen)
            {
                for(unsigned i=minLen;i<str.size();i++)
                {
                    tmp=str[i]+carry;
                    if(tmp>'9')
                    {
                        carry=1;
                        tmp-=10;
                    }
                    else
                    {
                        carry=0;
                    }
                    ret.str+=tmp;
                }
            }
            if(oprand.str.size()>minLen)
            {
                for(unsigned i=minLen;i<oprand.str.size();i++)
                {
                    tmp=oprand.str[i]+carry;
                    if(tmp>'9')
                    {
                        carry=1;
                        tmp-=10;
                    }
                    else
                    {
                        carry=0;
                    }
                    ret.str+=tmp;
                }
            }
            if(carry)
                ret.str+='1';
            return ret;
        }
        NumStr operator*(unsigned char oprand)
        {
            NumStr ret;
            unsigned char carry=0;
            unsigned char tmp;
            for(unsigned i=0;i<str.size();i++)
            {
                tmp=(str[i]-'0')*oprand+carry;
                ret.str+=(tmp%10+'0');
                carry=tmp/10;
            }
            if(carry!=0)
                ret.str+=(carry+'0');
            return ret;
        }
        NumStr operator*(NumStr oprand)
        {
            NumStr ret,tmpStr;
            for(unsigned i=0;i<oprand.str.size();i++)
            {
                if(oprand.str[i]!='0')
                {
                    tmpStr=*this*(oprand.str[i]-'0');
                    if(i>0)
                        tmpStr.str.insert(0,i,'0');
                    ret=ret+tmpStr;
                }
            }
            return ret;
        }
        void print()
        {
            for(int i=str.size()-1;i>=0;i--)
                cout<<str[i];
        }
    };
    const unsigned MAX = 100;
    NumStr y[MAX];//idx:0~99
    NumStr nP2[MAX];//idx:2~99
    NumStr nCm[MAX-2][(MAX-2)/2];
    void preDeal()
    {
        //init nP2
        NumStr idx("2");
        NumStr tmp=NumStr("1");
        NumStr one("1");
        unsigned i=2;
        while(i<MAX)
        {
            nP2[i++]=idx*tmp;
            tmp=idx;
            idx=idx+one;
        }
        //init nCm
        for(i=2;i<MAX-2;i++)
        {
            nCm[i][0]=NumStr("1");
        }
        tmp=NumStr("2");
        for(i=2;i<MAX-2;i++)
        {
            nCm[i][1]=tmp;
            tmp=tmp+one;
        }
        unsigned endCond;
        for(i=4;i<MAX-2;i++)
        {
            endCond=i/2;
            for(unsigned j=2;j<=endCond;j++)
            {
                if(j*2==i)
                {
                    nCm[i][j]=nCm[i-1][j-1]*2;
                }
                else
                {
                    nCm[i][j]=nCm[i-1][j]+nCm[i][j-1]-nCm[i-1][j-2];
                }
            }
        }
        //init y1
        y[0]=NumStr("1");
        y[1]=NumStr("2");
        y[2]=NumStr("01");
        y[3]=NumStr("48");
        idx=NumStr("4");
        unsigned j;
        bool flag=true;
        for(i=4;i<MAX;i++)
        {
            j=i-2;
            endCond=j/2;
            tmp=NumStr("0");
            for(unsigned k=1;k<=endCond;k++)
            {
                if(k==endCond && flag)
                {
                    tmp=tmp+(nCm[j][k]*y[k]*y[k]);
                }
                else
                {
                    tmp=tmp+(nCm[j][k]*y[k]*y[j-k]*2);
                }
            }
            tmp=(tmp+(y[j]*2))*nP2[i];
            y[i]=tmp+(y[i-1]*idx*2);
            flag=!flag;
            idx=idx+one;
        }
        //init y2

    }

    int main()
    {
        using namespace std;
        preDeal();

    //    unsigned endCond;
    //    for(unsigned i=2;i<=18;i++)
    //    {
    //        endCond=i/2;
    //        for(unsigned j=0;j<=endCond;j++)
    //        {
    //            nCm[i][j].print();
    //            cout<<'\t';
    //        }
    //        cout<<endl;
    //    }
        unsigned n;
        NumStr tmp;
        while(cin>>n)
        {
            tmp=NumStr(to_string(n));
            reverse(tmp.str.begin(),tmp.str.end());
            (y[n-1]*tmp).print();
            cout<<"\n";
        }
        return 0;
    }