[BZOJ1005][HNOI2008]明明的烦恼 数学+prufer序列+高精度

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int N;

 int A[],D[],cnt=;

 int sum=,q=;

 int pri[];

 int ans[],len;

 int main(){

     scanf("%d",&N);

     if(N==){

         int tmp;

         scanf("%d",&tmp);

         if(!tmp||tmp==-) puts("");

         else puts("");

         return ;

     }

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

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

         if(!A[i]){

             puts("");

             return ;

         }

         if(A[i]!=-){

             D[++cnt]=A[i]-;

             sum+=D[cnt];

         }

         else q++;

     }

     if(N<sum+){

         puts("");

         return ;

     }

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

         for(int j=;j<=D[i];j++){

             int tmp=j;

             for(int k=;k<=j&&tmp!=;k++)

                 while(tmp%k==){

                     pri[k]--;

                     tmp/=k;

                 }

         }

     for(int i=N--sum+;i+<=N;i++){

         int tmp=i;

         for(int j=;j<=i&&tmp!=;j++)

             while(tmp%j==){

                 pri[j]++;

                 tmp/=j;

             }

     }

     ans[]=;

     len=;

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

         while(pri[i]){

             for(int j=;j<=len;j++) ans[j]*=i;

             for(int j=;j<=len;j++){

                 ans[j+]+=ans[j]/;

                 ans[j]%=;

             }

             while(ans[len+]){

                 len++;

                 ans[len+]+=ans[len]/;

                 ans[len]%=;

             }

             pri[i]--;

         }

     }

     for(int i=;i++sum<=N;i++){

         for(int j=;j<=len;j++) ans[j]*=q;

         for(int j=;j<=len;j++){

             ans[j+]+=ans[j]/;

             ans[j]%=;

         }

         while(ans[len+]){

             len++;

             ans[len+]+=ans[len]/;

             ans[len]%=;

         }

     }

     for(int i=len;i>=;i--) printf("%d",ans[i]);

     return ;

 }

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1005

一个prufer序列可以唯一确定一棵生成树。而prufer序列可以确定节点的度数，反过来，通过度数就可以确定prufer序列的方案数。

具体怎么做贴个黄学长的题解接跑吧……

题解：http://hzwer.com/3272.html