[HNOI2008]明明的烦恼

2018-04-28

lolifamily

题解

树的prufer编码

详见Prufer 编码例题

Problem

题目描述

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

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

输入格式

第一行为 $𝑁 (0 < 𝑁 \leq 1000)$ ，接下来 $𝑁$ 行，第 $𝑖 + 1$ 行给出第 $𝑖$ 个节点的度数 $𝐷 𝑖$ ，如果对度数不要求，则输入 -1。

输出格式

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

输入

输出

1
2

说明 / 提示

两棵树分别为 1-2-3 和 1-3-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,n,m=0,sum=0;
67
  scanf("%d",&n);
68
  for(i=1;i<=n;++i)
69
  {
70
    scanf("%d",&d[i]);
71
    if(d[i]==-1)++m;
72
    else
73
    {
74
      --d[i];sum+=d[i];
75
    }
76
  }
77
  if(sum>n-2){printf("0\n");return 0;}
78
  Solve(n-2,1);
79
  Solve(n-sum-2,-1);
80
  for(i=1;i<=n;++i)
81
  {
82
    if(d[i]>0)Solve(d[i],-1);
83
  }
84
  ans[1]=1;
85
  for(i=1;i<=cnt;++i)
86
  {
87
    for(j=1;j<=num[i];++j)ans*=p[i];
88
  }
89
  for(i=1;i<=n-sum-2;++i)ans*=m;
90
  cout<<ans<<endl;
91
  return 0;
92
}