P2624 [HNOI2008]明明的烦恼

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 3.2k | 阅读时长 ≈ 3 分钟

P2624 [HNOI2008]明明的烦恼

传送门

洛谷

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

3
1
-1
-1

输出样例#1：

2

说明

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

分析

前置知识：$Prufer$数列。
众所周知，对于给定度数的无根树，共有$\cfrac{ (n-2)! }{ \prod_{i=1}^n (d_i-1)! }$情况。使用$Prufer$数列可以很方便的证明。
但本题不是这么简单。
首先考虑已知的条件，我们记$sum$为已知条件的和，$cnt$为已知条件个数。
很显然，只考虑已知度数的点组成的无根树的情况，共有$\cfrac{ sum! }{ \prod_{i=1}^{cnt} (d_i-1)!}$种情况，直接套开头的式子。
再考虑在总点数组成的$Prufer$数列中，由我们的已知点组成的$Prufer$子序列有多少种情况，显然，组合知识告诉我们，有$\dbinom{n-2}{sum}$种情况。
在考虑剩下的位置，所以要乘上$(n-cnt)^{n-2-sum}$。
化简一波：

发现一个很尴尬的问题，我们…似乎需要…高精度！！！
高精乘还好说，高精除就比较尴尬了。
弃疗
其实还有一个办法，质因数分解。
对于$n!$，如果$p$是一个质数，那么它的次数为

所以高精除就搞定了。
至于高精乘，打板子。

参考资料

$Prufer$数列

自为风月马前卒的 prufer序列笔记
xun的 prufer数列

本题题解

本校巨佬autoint的题解
TheLostWeak的题解
JMJST的题解
怡红公子的题解

代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1010
#define mod (int)1e6
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,cnt,sum,len=1,d[maxn],p[maxn],num[maxn],ans[maxn]={1};
void init()
{
	for(int i=2;i<=n;i++)
	{
		if(!p[i])p[++p[0]]=i;
		for(int j=1;j<=p[0]&&p[j]*i<=n;j++)
		{
			p[p[j]*i]=true;
			if(i%p[j]==0)break;
		}
	}
}
void decomp(int n,int f)
{
	for(int i=1;i<=p[0]&&p[i]<=n;i++)
		for(int j=n;j>=p[i];j/=p[i])
			num[i]+=j/p[i]*f;
}
void mul(int n)
{
	for(int i=0;i<len;i++)ans[i]*=n;
	for(int i=0;i<len;i++)
		if(ans[i]>=mod)
			ans[i+1]+=ans[i]/mod,ans[i]%=mod;
	if(ans[len])len+=1;
}
int main()
{
	n=read<int>();
	init();
	for(int i=1;i<=n;i++)
	{
		int tmp=read<int>();
		if(tmp==-1)continue;
		cnt+=1;
		if(tmp<=0||tmp>n-2)
		{
			puts("0");
			return 0;
		}
		sum+=tmp-1;
		d[++d[0]]=tmp;
	}
	if(d[0]>n-2)
	{
		puts("0");
		return 0;
	}
	decomp(n-2,1);
	decomp(n-2-sum,-1);
	for(int i=1;i<=d[0];i++)decomp(d[i]-1,-1);
	for(int i=1;i<=p[0];i++)
		while(num[i]--)
			mul(p[i]);
	for(int i=1;i<=n-2-sum;i++)mul(n-cnt);
	printf("%d",ans[len-1]);
	for(int i=len-2;i>=0;i--)printf("%06d",ans[i]);
    return 0;
}