1005: [HNOI2008]明明的烦恼

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 6539 Solved: 2558
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

3
1
-1
-1

Sample Output

HINT

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

首先要知道 Prufer数列和节点度数这种东西，自行Google。

Plufer数列有一下性质：

1、可以表示为任意一个长度为n-2的数列

2、任意一点的度数为d[i]，则该节点在数列中出现d[i]-1次

3、因此数列的总长度为：

\[sum=\sum _{i=1}^{n} (d[i]-1)\]

得出这个总长度的前提是，所有度数已知，但题目并没有给出所有的度数。但是我们可以计算出已知n个点的度数，可以构造出多少种Prufer数列：

\[\frac{(n-2)!}{\prod _{i-1}^{n}(d[i]-1)!}\]

那么已知cnt个点的度数，可以构造出多少种Prufer数列呢？

\[C_{n-2}^{sum}\times \frac{sum!}{\prod _{i-1}^{n}(d[i]-1)!}\]

那么已知cnt个点的度数，n-cnt个点的度数未知，可以构造出多少种Prufer数列呢？

\[ans=C_{n-2}^{sum}\times\frac{sum!}{\prod _{i-1}^{n}(d[i]-1)!}\times(n-cnt)^{n-2-sum}\]

最终可以化简得：

\[ans=\frac{(n-2)!}{(n-2-sum)!\prod _{i-1}^{n}(d[i]-1)!}\times(n-cnt)^{n-2-sum}\]

沿用了之前高精度乘除单精度的模板，减少代码量（明明是增加了）

虽说质因数分解更能显示bigger。。。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iomanip>

 using namespace std;

 const int MAXN=;

 const int DLEN=;

 const int WIDE=;

 class BigNum

 {

 public:

     int NUM[MAXN];

     int L;

     bool flag;

     BigNum(){memset(NUM,,sizeof(NUM));L=;flag=;}

     BigNum(const BigNum &T){memcpy(NUM,T.NUM,sizeof(NUM));L=T.L;flag=T.flag;}

     BigNum(int n){memset(NUM,,sizeof(NUM));NUM[]=n;L=;while(NUM[L-]>=WIDE){NUM[L]+=NUM[L-]/WIDE;NUM[L-]%=WIDE;L++;}flag=;}

 };

 void Output(const BigNum T)

 {

     if(T.flag==) cout<<'-';

     cout<<T.NUM[T.L-];

     for(int i=T.L-;i>=;i--)

     {

         cout.width(DLEN);

         cout.fill('');

         cout<<T.NUM[i];

     }

 }

 BigNum Mult(const BigNum A,int B)

 {

     BigNum C(A);

     int i,tmp,k=;

     for(i=;i<C.L||k;i++)

     {

         tmp=C.NUM[i]*B+k;

         k=tmp/WIDE;

         C.NUM[i]=tmp%WIDE;

     }

     C.L=i;

     return C;

 }

 BigNum Div(const BigNum A,int B)

 {

     BigNum C(A);

     int k=;

     for(int i=C.L-;i>=;i--)

     {

         k=k*WIDE+C.NUM[i];

         C.NUM[i]=k/B;

         k%=B;

     }

     while(C.NUM[C.L-]==) C.L--;

     return C;

 }

 int n,sum,cnt;

 int d[];

 bool flag;

 BigNum ans();

 int main()

 {

     scanf("%d",&n);

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

     {

         scanf("%d",&d[i]);

         if(d[i]==||d[i]>n-) flag=;

         if(d[i]==-) continue;

         sum+=d[i]-;

         cnt++;

     }

     if(n==)

     {

         if(d[]==||d[]==-) printf("1\n");

         else printf("0\n");

         return ;

     }

     if(n==)

     {

         if((d[]==||d[]>)&&(d[]==||d[]>)) printf("1\n");

         else printf("0\n");

         return ;

     }

     if(flag)

     {

         printf("0\n");

         return ;

     }

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

         ans=Mult(ans,i);

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

         ans=Mult(ans,n-cnt);

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

         for(int j=;j<=d[i]-;j++)

             ans=Div(ans,j);

     Output(ans);

     return ;

 }

巴特西