自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

一个整数,表示不同的满足要求的树的个数,无解输出0

两棵树分别为1-2-3;1-3-2

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 1010#define MAXL 1000#define VAL1 10000class number//四位{        public:                number()                {                        clear();                }                bool is_odd()                {                        return numb[0]%2==1;                }                bool is_even()                {                        return numb[0]%2==0;                }                void lsh_bin()                {                        int i;                        for (i=topn;i>0;i--)                        {                                if (numb[i]%2==1)                                {                                        numb[i-1]+=VAL1;                                }                                numb[i]/=2;                        }                        numb[0]/=2;                        while (topn&&!numb[topn])topn--;                }                bool equal_to(int x)                {                        if (topn==0)                        {                                return x==numb[0];                        }                        if (topn==1)                        {                                return x==numb[0]+numb[1]*VAL1;                        }                        return false;                }                int size()                {                        return topn;                }                int length()                {                        int x=numb[topn];                        int ret=0;                        while (x)                        {                                ret++;                                x/=10;                        }                        int y=0;                        x=VAL1;                        while (x)                        {                                y++;                                x/=10;                        }                        y--;                        ret+=topn*y;                        return ret;                }                void operator =(int x)//{{{                {                        int now=0;                        clear();                        numb[now]=x;                        while (numb[now]>=VAL1)                        {                                numb[now+1]+=numb[now]/VAL1;                                numb[now]%=VAL1;                                now++;                                if (now>topn)topn=now;                        }                }//}}}void operator =(number num)//{{{{        topn=num.topn;        memcpy((this->numb),num.numb,sizeof(num.numb[0])*(topn+1));}//}}}void operator +=(number &num)//{{{{        int i;        topn=max(topn,num.topn);        for (i=0;i<=topn;i++)        {                numb[i]+=num.numb[i];;                if (numb[i]>=VAL1)                {                        numb[i+1]+=numb[i]/VAL1;                        numb[i]%=VAL1;                }        }        while (numb[topn+1])        {                topn++;                numb[topn+1]+=numb[topn]/VAL1;                numb[topn]%=VAL1;        }}//}}}void operator +=(int x)//{{{{        int now=0;        if (topn==-1)topn=0;        numb[now]+=x;        while (numb[now]>=VAL1)        {                numb[now+1]+=numb[now]/VAL1;                numb[now]%=VAL1;                now++;                if (now>topn)topn=now;        }}//}}}void operator *=(int x)//{{{{        int i;        for (i=0;i<=topn;i++)        {                numb[i]*=x;        }        for (i=0;i<=topn;i++)        {                if (numb[i]>=VAL1)                {                        numb[i+1]+=numb[i]/VAL1;                        numb[i]%=VAL1;                }        }        while (numb[topn+1])        {                topn++;                numb[topn+1]+=numb[topn]/VAL1;                numb[topn]%=VAL1;        }}//}}}void operator *=(number &num){        number ret;        ret=(*this)*num;        (*this)=ret;}void operator -=(number &num)//{{{{        if (*this<num)throw "Error!\n->void operator -=(number &num)\n";        int i;        for (i=0;i<=topn;i++)        {                numb[i]-=num.numb[i];        }        for (i=0;i<=topn;i++)        {                while (numb[i]<0)                {                        numb[i]+=VAL1;                        numb[i+1]--;                }        }        while (topn&&!numb[topn])topn--;}//}}}void operator /=(int x){        int i;        int tot=0;        for (i=topn;i>=0;i--)        {                tot=tot*VAL1+numb[i];                numb[i]=tot/x;                tot%=x;        }        while (topn&&!numb[topn])topn--;}void operator --(int)//{{{{        if (topn==0&&numb[0]==0)throw "Error!\n->void operator --(int)\n";        int now=0;        numb[now]--;        while (numb[now]<0)        {                numb[now+1]--;                numb[now]+=VAL1;        }        while (topn&&!numb[topn])topn--;}//}}}private:int numb[MAXL];int topn;void clear(){        topn=0;        memset(numb,0,sizeof(numb));}friend bool operator <(number num1,number num2);friend bool operator <=(number num1,number num2);friend bool operator ==(number num1,number num2);friend ostream& operator <<(ostream &out,number &num);friend istream& operator >>(istream &in,number &num);friend number operator *(number &num1,number &num2);friend number operator *(number num,int x);friend number operator +(number num1,number num2);friend number operator +(number num1,int x);friend number operator -(number num1,number num2);//a=a+b远没有a+=b快};bool operator <(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)        {                return num1.topn<num2.topn;        }         int i;        for (i=num1.topn;i>=0;i--)        {                if (num1.numb[i]!=num2.numb[i])                {                        return num1.numb[i]<num2.numb[i];                }        }        return false;}//}}}bool operator <=(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)        {                return num1.topn<num2.topn;        }         int i;        for (i=num1.topn;i>=0;i--)        {                if (num1.numb[i]!=num2.numb[i])                {                        return num1.numb[i]<num2.numb[i];                }        }        return true;}//}}}bool operator ==(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)return false;        for (int i=0;i<=num1.topn;i++)        {                if (num1.numb[i]!=num2.numb[i])return false;        }        return true;}//}}}ostream& operator <<(ostream &out,number &num)//{{{{        int i;        out<<num.numb[num.topn];        for (i=num.topn-1;i>=0;i--)        {                //压六位时                //        if (num.numb[i]<100000)out<<"0";                //        if (num.numb[i]<10000)out<<"0";                if (num.numb[i]<1000)out<<"0";                if (num.numb[i]<100)out<<"0";                if (num.numb[i]<10)out<<"0";                out<<num.numb[i];        }        return out;}//}}}istream& operator >>(istream &in,number &num)//{{{{        string str;        in>>str;        int i;        num.clear();        for (i=(int)str.length()-1,num.topn=0;i>=0;i-=4,num.topn++)        {                if (i-3<str.length())                {                        num.numb[num.topn]=(str[i]-‘0‘)+10*(str[i-1]-‘0‘)+100*(str[i-2]-‘0‘)+1000*(str[i-3]-‘0‘);                }else                {                        if (i-2<str.length())num.numb[num.topn]+=100*(str[i-2]-‘0‘);                        if (i-1<str.length())num.numb[num.topn]+=10*(str[i-1]-‘0‘);                        if (i  <str.length())num.numb[num.topn]+=(str[i]-‘0‘);                }        }        num.topn--;        return in;}//}}}number operator *(number num,int x)//{{{{        number ret;        ret=num;        ret*=x;        return ret;}//}}}number operator * (number &num1,number &num2){        int i,j;        number ret;        ret.topn=num1.topn+num2.topn;        for (i=0;i<=num1.topn;i++)        {                for (j=0;j<=num2.topn;j++)                {                        ret.numb[i+j]+=num1.numb[i]*num2.numb[j];                        if (ret.numb[i+j]>=VAL1)                        {                                ret.numb[i+j+1]+=ret.numb[i+j]/VAL1;                                ret.numb[i+j]%=VAL1;                        }                }        }        for (i=0;i<=ret.topn;i++)        {                if (ret.numb[i]>=VAL1)                {                        ret.numb[i+1]+=ret.numb[i]/VAL1;                        ret.numb[i]%=VAL1;                }        }        while (ret.numb[ret.topn+1])        {                ret.topn++;                ret.numb[ret.topn+1]+=ret.numb[ret.topn]/VAL1;                ret.numb[ret.topn]%=VAL1;        }                return ret;}number operator +(number num1,number num2)//{{{{        number ret;        ret=num1;        ret+=num2;        return ret;}//}}}number operator +(number num1,int x)//{{{{        number ret;        ret=num1;        ret+=x;        return ret;}//}}}number operator -(number num1,number num2)//{{{{        number ret;        ret=num1;        ret-=num2;        return ret;}//}}}number c (int x,int y){        number ret;        ret=1;        int i;        for (i=y+1;i<=x;i++)                ret*=i;        for (i=1;i<=(x-y);i++)                ret/=i;        return ret;}int main(){        freopen("input.txt","r",stdin);        int x;        int n;        scanf("%d",&n);        number ans;        number temp1,temp2,temp3;//        number temp;//        temp=c(1000,2);//        cout<<temp<<endl;        ans=1;        int r=n-2;        int i,j;        j=1;        int totu=0;        for (i=0;i<n;i++)        {                scanf("%d",&x);                if (x==0)                {                        printf("0\n");                        return 0;                }                if (x!=-1)                {                        if (!r&&x-1)                        {                                printf("0\n");                                return 0;                        }                        temp1=c(r,x-1);                        ans*=temp1;                        r-=x-1;                        if (r<0)                        {                                printf("0\n");                                return 0;                        }                }else                {                        totu++;                }        }        if (r&&totu<=0)        {                printf("0\n");                return 0;        }        if (r)        {                for (i=1;i<=r;i++)                {                        ans=ans*totu;                }        }        cout<<ans<<endl;}