[bzoj1005] [洛谷P2624] 明明的烦恼

Description

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

Input

第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

3
1
-1
-1

Sample Output

2

HINT

两棵树分别为1-2-3;1-3-2

想法

这道题用了一个叫做prufer编码的东西（新技能get）

首先prufer编码是啥呢？
引用一下怡红公子的话：
“
该题运用到了树的prufer编码的性质：
(1)树的prufer编码的实现
不断 删除树中度数为1的最小序号的点，并输出与其相连的节点的序号 直至树中只有两个节点
(2)通过观察我们可以发现
任意一棵n节点的树都可唯一的用长度为n-2的prufer编码表示
度数为m的节点的序号在prufer编码中出现的次数为m-1
(3)怎样将prufer编码还原为一棵树？？
从prufer编码的最前端开始扫描节点，设该节点序号为 u ,寻找不在prufer编码的最小序号且没有被标记的节点 v ，连接 u,v,并标记v，将u从prufer编码中删除。扫描下一节点。
”
这个东西自己画一下挺好理解的。

感觉它最神奇的一点就是这n-2位的编码可以随便填，没有特殊的限制，一个编码就能对应一棵树
一开始我想的是现在n个点中选一个点当根，然后剩余n-1个点都选一个自己的父节点，根据度数判断这个点是多少个点的父节点，但这样有一些问题，比如可能出现环。
而prufer编码就不会出现这样的问题了。

如果我们知道了每个点的度数d[i]
那么满足的树的个数（即prufer编码个数）为 \(\frac{(n-2)!}{\prod(d[i]-1)!}\)
但是题目中有一些点的度数是不知道的。设知道度数的点有m个，它们的 \(\sum d[i]-1\) 为s
那么满足的树的个数为
$
\frac{s!}{\prod(d[i]-1)!} \times C_{n-2}^s \times (n-m)^{n-2-s} \
=\frac{(n-2)!}{\prod(d[i]-1)! \times (n-2-s)!} \times (n-m)^{n-2-s}
$
注意要高精度

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1005;
const int SZ = 1000;

int n;
int d[N];

struct Bint{
    int a[N];
    int s;
    Bint operator * (const int &b) const{
        Bint c;
        int g=0,f;
        for(int i=0;i<s;i++){
            f=g+a[i]*b;
            c.a[i]=f%SZ;
            g=f/SZ;
        }
        if(g) c.a[s]=g,c.s=s+1;
        else c.s=s;
        return c;
    }
    Bint operator / (const int &b) const{
        Bint c;
        int g=0,f;
        for(int i=s-1;i>=0;i--){
            f=g*SZ+a[i];
            c.a[i]=f/b;
            g=f%b;
        }
        c.s=s;
        while(c.s && c.a[c.s-1]==0) c.s--;
        return c;
    }
    Bint operator *= (const int &b) { return *this=*this*b; }
    Bint operator /= (const int &b) { return *this=*this/b; }
    void output(){ //注意
        printf("%d",a[s-1]);
        for(int i=s-2;i>=0;i--) {
            if(a[i]==0) printf("000");
            else if(a[i]<10) printf("00%d",a[i]);
            else if(a[i]<100) printf("0%d",a[i]);
            else printf("%d",a[i]); 
        }
        printf("\n");
    }
}ans;

int main()
{
    int s=0,m=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
        if(d[i]!=-1) m++,s+=d[i]-1;
    }
    
    ans.a[0]=1; ans.s=1;
    for(int i=n-s-1;i<=n-2;i++) ans*=i;
    for(int i=1;i<=n;i++) if(d[i]>1) {
        for(int j=2;j<=d[i]-1;j++) ans/=j;
    }
    for(int i=0;i<n-s-2;i++) ans*=(n-m);
    
    ans.output();
    
    return 0;
}