BZOJ-1005 明明的烦恼题解(Prufer序列+高精度)

Description

传送门:BZOJ-1005

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


Input

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

Output

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

Sample Input

1
2
3
4
3
1
-1
-1

Sample Output

1
2

Hint

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

题目大意

给定一些点的度数,求任意两点之间可以连线,求可以生成的树的个数

思路

Prufer序列,每一个Prufer序列对应一颗树,Prufer序列的长度为n-2,Prufer序列的性质之一就是每个点在Prufer序列中出现的次数为度数-1,没出现代表叶子节点。更多请查看Prufer。我们就可以根据度数来统计树的个数。假设有\(cnt\)个点有度数限制,我们记\(\displaystyle sum = \sum_{i=1}^{cnt}(d[i]-1)\)。那么对于给定度数的点,我们可以知道这\(cnt\)个点在Prufer序列中的摆放方案有\(\displaystyle C_{n-2}^{sum} * \frac{sum!}{\prod_{i=1}^{cnt}(d[i]-1)!}\)

然后对于剩下的\(n-cnt\)个点,在剩下的\(n-sum-2\)个位置中的摆放位置有\((n-cnt)^{n-sum-2}\)种,根据乘法原理,所有的方案数一共为\(\displaystyle C_{n-2}^{sum} * \frac{sum!}{\prod_{i=1}^{cnt}(d[i]-1)!}*(n-cnt)^{n-sum-2}\)。再化简一下可以得到\(\displaystyle \frac{(n-2)!}{(n-sum-2)!*\prod(d[i]-1)!}*(n-cnt)^{n-sum-2}\),需要注意的是需要高精度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/************************************************************
> File Name: 1005.cpp
> Author: TSwiftie
> Mail: 2224273204@qq.com
> Created Time: Mon 06 Jan 2020 04:09:07 PM CST
************************************************************/

#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
#define lowbit(x) (x&-x)
#define lc (o<<1)
#define rc (o<<1|1)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e3+5;
const int MAXM = 2e5+5;
const int MOD = 1e9+7;
const int dir[4][2] = {1,0,-1,0,0,1,0,-1};
const double PI = acos(-1.0);
const double EXP = 1e-8;
int d[MAXN];
//高精度模板
struct BigInt{
int a[7000],len;
BigInt(){
memset(a,0,28000);
len = 1;
}
BigInt operator * (const int &rhs) const{
BigInt ans;
ans.len = len + 6;
for(int i = 1;i <= len;i++)
ans.a[i] += a[i] * rhs;
for(int i = 1;i < ans.len;i++)
if(ans.a[i] > 9){
ans.a[i+1] += ans.a[i] / 10;
ans.a[i] %= 10;
}
while(!ans.a[--ans.len]);
return ans;
}
BigInt operator / (const int &rhs) const{
BigInt ans;
ans = *this,++ans.len;
for(int i = ans.len;i;i--){
ans.a[i-1] += ans.a[i]%rhs*10;
ans.a[i] /= rhs;
}
while(!ans.a[--ans.len]);
return ans;
}
};
int main(void){
int n, sum = 0, cnt = 0;
BigInt ans;
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",d+i);
if(!d[i]){//一棵树没有度数为0的节点
puts("0");
return 0;
}
if(~d[i])
++ cnt,sum += d[i]-1;
}
if(sum > 2*n-2){//图的度数等于边数的两倍
puts("0");
return 0;
}
ans.a[1] = 1;
for(int i = n-1-sum;i < n-1;i++)
ans = ans * i;
for(int i = 1;i <= n-2-sum;i++)
ans = ans * (n - cnt);
for(int i = 1;i <= n;i++)
for(int j = 2;j <= d[i]-1;j++)
ans = ans / j;
for(int i = ans.len;i;i--)
printf("%d",ans.a[i]);
puts("");
return 0;
}

本文标题:BZOJ-1005 明明的烦恼题解(Prufer序列+高精度)

文章作者:TSwifite

发布时间:2020年01月06日 - 16:01

最后更新:2020年01月06日 - 16:01

原始链接:http://tswiftie.com/BZOJ-1005-明明的烦恼题解-Prufer序列-高精度/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%