[HNOI2004]树的计数

2018-04-28

lolifamily

题解

树的prufer编码

注意点：

度数为 $0$ 一定无解
度数减一的和不等于点数 $- 2$ 一定无解
数据保证满足条件的树不超过 $1017$ 个，但要用高精 ~~（然而并不需要，呵呵）~~

其他的就跟模板题一样了～

Problem

题目描述

一个有 $𝑛$ 个结点的树，设它的结点分别为 $𝑣 1, 𝑣 2, \dots, 𝑣 𝑛$ ，已知第 $𝑖$ 个结点 $𝑣 𝑖$ 的度数为 $𝑑 𝑖$ ，问满足这样的条件的不同的树有多少棵。

给定 $𝑛, 𝑑 1, 𝑑 2, \dots, 𝑑 𝑛$ ，编程需要输出满足 $𝑑 (𝑣 𝑖) = 𝑑 𝑖$ 的树的个数。

输入格式

第一行是一个正整数 $𝑛$ ，表示树有 $𝑛$ 个结点。

第二行有 $𝑛$ 个数，第 $𝑖$ 个数表示 $𝑑 𝑖$ ，即树的第 $𝑖$ 个结点的度数。

其中 $1 \leq 𝑛 \leq 150$ ，输入数据保证满足条件的树不超过 $1017$ 个。

输出格式

输出满足条件的树有多少棵。

输入

输出

1
2

Code

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
struct bigint
7
{
8
    mutable int a[1005];
9
    inline int& operator[](size_t pos)const{return a[pos];}
10
    inline bigint(){memset(a,0,sizeof(a));a[0]=1;}
11
    inline bigint& operator*=(int b)
12
    {
13
        int i;
14
        for(i=1;i<=a[0];++i)a[i]*=b;
15
        for(i=1;i<=a[0]||a[i];++i)
16
        {
17
            if(a[i]>=10000)
18
            {
19
                a[i+1]+=a[i]/10000;
20
                a[i]%=10000;
21
            }
22
        }
23
        a[0]=i-1;
24
        return *this;
25
    }
26
}ans;
27
inline ostream& operator<<(ostream& os,const bigint& a)
28
{
29
    printf("%d",a[a[0]]);
30
    for(int i=a[0]-1;i>=1;--i)printf("%04d",a[i]);
31
    return os;
32
}
33
int num[1005],d[1005],p[1005],cnt;
34
bool vis[1005];
35
inline void Solve(int x,int del)
36
{
37
    int i,j,s;
38
    for(i=1;i<=cnt&&p[i]<=x;++i)
39
    {
40
        s=p[i];
41
        while(s<=x)
42
        {
43
            num[i]+=(x/s)*del;
44
            s*=p[i];
45
        }
46
    }
47
    return;
48
}
49
inline void Init()
50
{
51
    int i,j;
52
    for(i=2;i<=1000;++i)
53
    {
54
        if(!vis[i])p[++cnt]=i;
55
        for(j=1;j<=cnt&&i*p[j]<=1000;++j)
56
        {
57
            vis[i*p[j]]=1;
58
            if(i%p[j]==0)break;
59
        }
60
    }
61
    return;
62
}
63
int main(void)
64
{
65
    Init();
66
    int i,j,x,n,m=0;
67
    long long sum=0;
68
    scanf("%d",&n);
69
    if(n==1)
70
    {
71
        scanf("%d",&x);
72
        if(!x)printf("1\n");
73
        else printf("0\n");
74
        return 0;
75
    }
76
    for(i=1;i<=n;++i)
77
    {
78
        scanf("%d",&d[i]);
79
        if(d[i]==0){printf("0\n");return 0;}
80
        --d[i];sum+=d[i];
81
    }
82
    if(sum!=n-2){printf("0\n");return 0;}
83
    Solve(n-2,1);
84
    Solve(n-sum-2,-1);
85
    for(i=1;i<=n;++i)
86
    {
87
        if(d[i]>0)Solve(d[i],-1);
88
    }
89
    ans[1]=1;
90
    for(i=1;i<=cnt;++i)
91
    {
92
        for(j=1;j<=num[i];++j)ans*=p[i];
93
    }
94
    for(i=1;i<=n-sum-2;++i)ans*=m;
95
    cout<<ans<<endl;
96
    return 0;
97
}