Bzoj1005 [HNOI2008]明明的烦恼

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 4948  Solved: 1926

Description

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

Input

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

Output

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

Sample Input

3
1
-1
-1

Sample Output

2

HINT

 

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

 

Source

 

数学问题 组合数  高精度 树 prufer序列

利用一个prufer序列对应唯一的树结构这一性质，进行花式组合计算

为了回避麻烦的高精度除法，可以分解质因数，用减指数代替直接除，最后再把各质数乘起来。

答案蜜汁长，2000位高精度WA掉了，压了两位就过了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=1010;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Num{
    int x[2001],len;
    void read(int a){
        len=0;
        while(a){x[++len]=a%100;a/=100;}
        return;
    }
    inline int max(int a,int b){return a>b?a:b;}
    void operator * (int b){
        for(int i=1;i<=len;i++)
            x[i]*=b;
        for(int i=1;i<=len;i++)
            if(x[i]>9){
                x[i+1]+=x[i]/100;
                x[i]%=100;
                len=max(len,i+1);
            }
        return;
    }
}a;
void Print(Num a){
    while(!a.x[a.len])a.len--;
    for(int i=a.len;i;i--)
        if(i==a.len)printf("%d",a.x[i]);
        else printf("%02d",a.x[i]);
    puts("");
    return;
}
int pri[mxn],cnt=0;
bool vis[mxn];
void init(){
    for(int i=2;i<mxn;i++){
        if(!vis[i])pri[++cnt]=i;
        for(int j=1;j<=cnt && pri[j]*i<mxn;j++){
            vis[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
    return;
}
int p[mxn],d[mxn],n,m,smm=0;
void calc(int x,int f){
//    printf("calc:%d %d\n",x,f);
    for(int i=1;i<=cnt && pri[i]<=x;i++){
        while(x%pri[i]==0){
            p[i]+=f;
            x/=pri[i];
        }
    }
    return;
}
int main(){
//    freopen("bzoj_100511.in","r",stdin);
//    freopen("bzoj_1005.out","w",stdout);
    int i,j;
    init();
    n=read();
    if(n==1){
        i=read();
        if(!i || i==-1)printf("1\n");
        else printf("0\n");
        return 0;
    }
    for(i=1;i<=n;i++){
        d[i]=read();
        if(!d[i]){
            printf("0\n");return 0;
        }
        if(d[i]!=-1)smm+=d[i]-1;
        else m++;
    }
    if(smm>n-2 || !m){
        printf("0\n");return 0;
    }
    for(i=n-2;i>1;i--)calc(i,1);
    calc(m,n-2-smm);
    for(i=n-2-smm;i>1;i--)calc(i,-1);
    for(i=1;i<=n;i++){
        for(j=d[i]-1;j>1;j--){
            calc(j,-1);
        }
    }
    a.read(1);
    for(i=1;i<=cnt;i++){
        for(j=1;j<=p[i];j++)
            a.operator *(pri[i]);
    }
    Print(a);
    return 0;
}