[BZOJ 1005] 明明的烦恼

标签：组合数 Prufer序列

题意

给出一棵树上某些点的度数（-1 就是不限制度数）

求有多少种不同的树的个数

题解

要做这道题首先得知道Prufer序列。

每一个这样的序列都对应着一棵树。

同时每个点的度数减1 就是Prufer序列上这个点的出现次数。

然后用组合数搞一搞就行了。

这题要用高精度。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             using namespace std;#define ll long long#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)inline int read(){ int sum=0,p=1;char ch=getchar(); while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar(); if(ch=='-')p=-1,ch=getchar(); while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar(); return sum*p;}const int maxn=1e3+20;int n,a[maxn],sum,num;int prime[maxn],cnt,mark[maxn];void prepare(){ REP(i,2,1000) { if(!mark[i])prime[++cnt]=i,mark[i]=cnt; for(int j=1;j<=cnt && prime[j]*i<=1000;j++) { mark[i*prime[j]]=1; if(!(i % prime[j]))break; } }}int s[maxn];void fj(int x,int add){ int j=1; while(prime[j]*prime[j]<=x) { while(!(x % prime[j]))x/=prime[j],s[j]+=add; j++; } if(x>1)s[mark[x]]+=add;}void init(){ n=read(); REP(i,1,n) { a[i]=read(); if(a[i]==-1)num++;else sum+=a[i]-1; if(!a[i]) { cout<<0<
              
               n-2) { cout<<0<
               
                1)REP(j,1,a[i]-1)fj(j,-1); } fj(num,n-2-sum);}int cj[maxn*10],len=1;void doing(){ cj[1]=1; REP(i,1,cnt) { if(s[i]) { REP(j,1,s[i]) { REP(l,1,len) { cj[l]*=prime[i]; } len+=4; REP(l,1,len) { cj[l+1]+=cj[l]/10; cj[l]%=10; } while(!cj[len])len--; } } } DREP(i,len,1)cout<