[prufer序列]BZOJ1005: [HNOI2008]明明的苦恼

[prufer序列]BZOJ1005: [HNOI2008]明明的烦恼

1005: [HNOI2008]明明的烦恼

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1909 Solved: 746
[Submit][Status]

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

Source

首先介绍一下Prufer序列

rufer数列是无根树的一种数列。在组合数学中，Prufer数列由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的Prufer数列长度为n-2。它可以通过简单的迭代方法计算出来。

以上引自百度百科

结点在Prufer序列中的出现次数其实就等于结点度数-1

那么这就成了一道排列组合题

首先计算tot=sigma(D(s)-1)

S为所有对度数有限制的节点，D为度数

之后我们要为他们选择tot个位置

所以有C(tot,n-2)个位置的可能

然后tot个数有tot!种排列

然后去重，对于所有有度数要求的非叶子节点S，tot/(d(s)-1)!

然后还剩下n-2-tot个位置

计算一下有K个节点没有度数限制

接下来这n-2-tot个位置可以*摆放

所以答案=C(tot,n-2)* tot!/连乘(d(s)-1)! *k^(n-2-tot)

还要写高精，真蛋疼

/**************************************************************
    Problem: 1005
    User: SKYDEC
    Language: C++
    Result: Accepted
    Time:72 ms
    Memory:4800 kb
****************************************************************/
 
#include<stdio.h>
using namespace std;
long f[1010][1010];
long now[1010];
long n;long w[1010];
long tot;bool fail=true;
long gj[1010];
long does(long x)
{
     long u=x;bool flag=true;
     while((u!=1)&&flag)
     {
                flag=false;
                for(long i=2;i*i<=u;i++)
                if(u%i==0)
                {
                          while(u%i==0)
                          {
                                       f[x][i]++;
                                       u/=i;
                                       }
                          flag=true;
                          break;
                          }
                          }
     if(u!=1)f[x][u]++;
}
long add(long x)
{
     for(long i=1;i<=1000;i++)
     now[i]+=f[x][i];
}
long dec(long x)
{
     for(long i=1;i<=1000;i++)
     now[i]-=f[x][i];
}
void mult(long x)
{
     for(long i=1;i<=gj[0];i++)gj[i]*=x;
     for(long i=1;i<=gj[0];i++){gj[i+1]+=gj[i]/10000;gj[i]%=10000;}
     while(gj[gj[0]+1]>0)
     {
                         gj[0]++;
                         gj[gj[0]+1]+=gj[gj[0]]/10000;
                         gj[gj[0]]%=10000;
                         }
}
void calc()
{
     gj[0]=1;gj[1]=1;
     for(long i=1;i<=1000;i++)
     for(long j=1;j<=now[i];j++)mult(i);
     for(long i=gj[0];i>=1;i--)
     {
              if(i!=gj[0])
              {
               if(gj[i]<10)printf("000");
               else if(gj[i]<100)printf("00");
               else if(gj[i]<1000)printf("0");
               }
              printf("%ld",gj[i]);
              }
}
int main()
{
    //freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
    scanf("%ld",&n);for(long i=1;i<=n;i++)scanf("%ld",&w[i]);
    tot=0;
    for(long i=1;i<=n;i++)
    {
             if(w[i]!=-1)tot+=w[i]-1;
             if((w[i]==0)||(w[i]>n-1))fail=false;
             }
    if(n==1)
    {
            if(tot==0)printf("1");else printf("0");
            return 0;
            }
    if(n==2)
    {
            if(w[1]==-1)
            {
                        if(!(w[2]==1||w[2]==-1||w[2]==2)){printf("0");return 0;}
                        }
            else
            if(w[1]==1)
            {
                       if(!(w[2]==-1||w[2]==2)){printf("0");return 0;}
                       }
            else
            if(w[1]==2)
            {
                       if(!(w[2]==1||w[2]==-1)){printf("0");return 0;}
                       }
            else {printf("0");return 0;}
                       }
    if(!fail){printf("0");return 0;}
    for(long i=1;i<=n;i++)does(i);
    for(long i=1;i<=n-2;i++)add(i);
    for(long i=1;i<=n-2-tot;i++)dec(i);
    for(long i=1;i<=n;i++)
    if(w[i]>1)for(long j=1;j<=w[i]-1;j++)dec(j);
    long tan=0;for(long i=1;i<=n;i++)if(w[i]==-1)tan++;
    for(long i=1;i<=n-2-tot;i++)add(tan);
    calc();
    return 0;
}