【prufer编码+组合数学】BZOJ1005 [HNOI2008]明明的烦恼

Description

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

Solution

　　这道题就是树的计数加强版，多了不要求的情况。

　　对于已限制的情况，就是C(n-2,t)*可重复元素的公式，考虑其他不限制的元素，再*(n-t)^(n-2-sum)，t为已限制点个数，sum为已限制度数。

　　大概就是这个意思，计算要用分解质因数+高精度，具体细节自己推一推。

Code

　　因为是高精乘低精，高精度很好打。

　　1A十分感动，感觉最近打代码没以前那么无脑了。

　　

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int maxn=5e3+;

 int dy[maxn],pri[maxn],tot[maxn],cnt;

 int a[maxn],d[maxn],n,t,len;

 int getpri(){

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

         if(!dy[i]) pri[++cnt]=i,dy[i]=cnt;

         for(int j=;j<=cnt&&pri[j]*i<=n;j++){

             dy[pri[j]*i]=j;

             if(i%pri[j]==) break;

         }

     }

 }

 int add(int x,int k){

     while(x!=){

         tot[dy[x]]+=k;

         x/=pri[dy[x]];

     }

 }

 int mul(int x){

     for(int i=;i<=len;i++) a[i]*=x;

     for(int i=;i<=len;i++) if(a[i]>=){

         if(i==len) len++;

         a[i+]+=a[i]/;

         a[i]%=;

     }

 }

 int main(){

     int sum=;

     scanf("%d",&n);

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

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

         if(d[i]!=-) sum+=d[i]-;

     }

     if(sum>n-){

         printf("0\n");

         return ;

     }

     if(n==){

         printf("1\n");

         return ;

     }

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

         if(!d[i]){

             printf("0\n");

             return ;

         }

         if(d[i]!=-) t++;

     }

     getpri();

     for(int i=;i<=n-;i++) add(i,);

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

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

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

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

     len=a[]=;

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

         for(int j=;j<=tot[i];j++) mul(pri[i]);

     for(int i=len;i>=;i--)

         printf("%d",a[i]);

     return ;

 }