洛谷 P2624/bzoj 1005 [HNOI2008]明明的烦恼 题解 【prufer数列】【高精度】【组合数学】

点击量：196

    prufer数列的入门，这个题需要一定的代码技巧。

目录

题目描述

自从明明学了树的结构，就对奇怪的树产生了兴趣……

给出标号为\(1\)到\(N\)的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树？

输入输出格式

输入格式：

第一行为\(N(0<N\le 1000)\)，

接下来\(N\)行，第\(i+1\)行给出第\(i\)个节点的度数\(D_i\)，如果对度数不要求，则输出\(-1\)。

输出格式：

一个整数，表示不同的满足要求的树的个数，无解输出\(0\)。

输入输出样例

输入样例：

3
1
-1
-1

输入样例：

2

说明

两棵树分别为\(1-2-3,1-3-2\)。

题解：

    prufer数列和无根树的形态是一一对应的。有一个讲得比较好的博客prufer数列可以参考。大致上就是对树从叶子节点进行优先队列拓扑排序，通过节点编号从小到大删点并记录父亲的过程。最后整棵树会剩下两个节点，因为如果把这两个节点加入数列，造成的结果是一样的，还平添了数列长度。因此做到只剩两个点时就停止。恢复时，假设当时处理到数列中第\(i\)个位置，就要找在\([i,n-2]\)这一段中没有出现过，且还没有被找过的最小的数，然后把这个数与第\(i\)个位置的点连边。形式化地说就是每次找到\(A={1,2,\dots,n}\)与\(B[i,n-2]\)的补集的交集中的最小数，把它在\(A\)中删掉，然后把这个数与\(B_i\)连边。

    可以看出，在prufer数列中，对于一个度为\(d_i\)的点，它一定会出现\(d_i-1\)次，因为它有一条边是指向父亲的，其余的边都由儿子指向自己。那么在本题中出现\(d_i-1\)次就意味着prufer数列中有且仅有\(d_i-1\)个位置是\(i\)，且\(d_i\ne -1\)。此时想像一个长为\(n-2\)的数组中全部是空的，那么我们已经固定了\(m=\sum_{i=1,d_i\ne -1}^n(d_i-1)\)个数，就要先把它们填写进来，方案数为\(\frac{(n-2)!}{n-2-m}\)。但是注意这里有重复元素，每个元素会出现\(d_i-1(d_i\ne -1)\)次。因此还要在分母上乘\(\prod_{i=1,d_i\ne -1}^n((d_i-1)!)\)。最后除了固定的元素，还有\(n-2-m\)个位置没有填元素，那么对于\(d_i=-1\)的元素，就可以任意放入其中，方案数在最后乘上\(cnt^{n-m-2}\)即可。（\(cnt=\sum_{i=1}^n[d_i=-1]\)）。

    但是这个题需要高精，答案的位数可能达到\(3,000\)位。高精度除法比较烦，但是注意到这里只用除\(1000\)以内的数，因此我们以\(10^4\)的数量级压位，就可以轻松把一次除法做到\(O(\lg ans)\)的时间复杂度。

    总时间复杂度为\(O(\lg n!\sum_{i=1}^nd_i)\)。

    还有两道水题：洛谷P4430，洛谷P2290这道题同时考察了数学技巧。

Code：

#include<cstdio>
#include<cstring>
int Max(int x,int y)
{
    return x>y?x:y;
}
struct lll
{
    int num[1000];
    lll(int x)
    {
        memset(num,0,sizeof(num));
        num[0]=1+(x/10000>0);
        num[1]=x%10000;
        num[2]=x/10000;
    }
    lll()
    {
        memset(num,0,sizeof(num));
    }
    void print()
    {
        printf("%d",num[num[0]]);
        for(int i=num[0]-1;i;--i)
        {
            if(num[i]<1000)
                printf("0");
            if(num[i]<100)
                printf("0");
            if(num[i]<10)
                printf("0");
            printf("%d",num[i]);
        }
        puts("");
    }
    
};
bool operator <(lll a,lll b)
{
    if(a.num[0]!=b.num[0])
        return a.num[0]<b.num[0];
    for(int i=a.num[0];i;--i)
        if(a.num[i]!=b.num[i])
            return a.num[i]<b.num[i];
    return false;
}
bool operator >(lll a,lll b)
{
    return !(a<b);
}
lll operator +(lll a,lll b)//高精+高精
{
    a.num[0]=Max(a.num[0],b.num[0])+1;
    for(int i=1;i<=a.num[0];++i)
    {
        a.num[i]+=b.num[i];
        if(a.num[i]>=10000)
        {
            a.num[i+1]=1;
            a.num[i]-=10000;
        }
    }
    while(!a.num[a.num[0]]&&a.num[0]>1)
        --a.num[0];
    return a;
}
lll operator -(lll a,lll b)//高精-高精
{
    for(int i=1;i<=a.num[0];++i)
    {
        a.num[i]-=b.num[i];
        if(a.num[i]<0)
        {
            a.num[i]+=10000;
            --a.num[i+1];
        }
    }
    while(!a.num[a.num[0]]&&a.num[0]>1)
        --a.num[0];
    return a;
}
lll operator *(lll a,lll b)//高精*高精
{
    lll c(0);
    c.num[0]=a.num[0]+b.num[0];
    for(int i=1;i<=a.num[0];++i)
        for(int j=1;j<=b.num[0];++j)
        {
            c.num[i+j-1]+=a.num[i]*b.num[j];
            c.num[i+j]+=c.num[i+j-1]/10000;
            c.num[i+j-1]%=10000;
        }
    while(!c.num[c.num[0]]&&c.num[0]>1)
        --c.num[0];
    return c;
}
lll operator /(lll a,int b)高精/低精
{
    for(int i=a.num[0];i;--i)
    {
        int tmp=a.num[i]%b;
        a.num[i]/=b;
        if(i>1)
            a.num[i-1]+=tmp*10000;
    }
    while(!a.num[a.num[0]]&&a.num[0]>1)
        --a.num[0];
    return a;
}
lll qpow(lll a,int x)//高精快速幂
{
    lll ans(1);
    while(x)
    {
        if(x&1)
            ans=ans*a;
        a=a*a;
        x>>=1;
    }
    return ans;
}
int d[1010];
int main()
{
    int n,cnt,m=0;//m表示有多少位置被占了
    scanf("%d",&n);
    cnt=n;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&d[i]);
        if(d[i]==0)
        {
            puts("0");
            return 0;
        }
        if(d[i]>0)
        {
            m+=d[i]-1;
            --cnt;
        }
    }
    if(m>n-2)//不合法（数据中没有这种情况）
    {
        puts("0");
        return 0;
    }
    lll ans(1);
    for(int i=n-2;i>n-2-m;--i)
        ans=ans*lll(i);
    ans=ans*qpow(lll(cnt),n-2-m);
    for(int i=1;i<=n;++i)
        for(int j=2;j<=d[i]-1;++j)
            ans=ans/j;//注意阶乘不要弄掉了
    ans.print();
    return 0;
}