问题描述
自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?
输入格式
第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
输出格式
一个整数,表示不同的满足要求的树的个数,无解输出0
样例输入
3
1
-1
-1
样例输出
2
样例解释
两棵树分别为1-2-3;1-3-2
解析
接下来我们需要使用Purfer Sequence。
Purfer Sequence
将一棵无根树按照以下原则构造出来的序列称为这棵树的Purfer Sequence。若树的大小为n，则这样的序列长度为n-2。
原则：每次找到当前树中度数为1的、编号最小的点，将这个点的父亲加入序列中，同时将这个点从树上删去
这个序列有许多性质，比如每个Purfer Sequence 对应唯一的一棵无根树。但是，我们要用的是另一个非常重要的性质：
对于树上的每一个节点(i)，设度数为(d_i)，那么(i)在序列中会出现(d_i-1)次。
有了这个性质之后，再看这道题。假设我们已经知道了每个点的度数，那么满足条件的无根树的方案数为：
这就是一个可重排列的公式。但是，现在有些点是没有限制的，而序列长度只能是(n-2)。所以，记：
那么，一个合法的方案就是在(n-2)个位置中选择(sum)个，这些位置进行可重排列。剩下的位置可以在(n-cnt)个点中随便放。方案数为：
化简可得：
当然，单是这么写还需要高精度乘除法。我们可以利用质因数分解，将最后的答案变为质因数相乘的形式，然后就可以用高精度乘低精度计算了。
注意，Purfer Sequence 可以解决大部分与度数有关的树的计数问题。
PS：以上关于Purfer Sequence的解释过于简陋，如需详解可以百度
代码
#include <iostream>
#include <cstdio>
#define N 1000002
using namespace std;
int n,sum,cnt,i,j,k,d[N],p[N],c[N],num,ans[N],l;
bool vis[N];
int read()
{
char c=getchar();
int w=0,f=1;
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w*f;
}
void change(int x,int op)
{
for(int i=1;i<=num;i++){
while(x%p[i]==0) c[p[i]]+=op,x/=p[i];
}
}
int main()
{
n=read();
for(i=2;i<=1000;i++){
if(!vis[i]){
p[++num]=i;
for(j=i;j<=1000;j+=i) vis[j]=1;
}
}
for(i=1;i<=n;i++){
d[i]=read();
if(d[i]!=-1){
cnt++;sum+=d[i]-1;
for(j=2;j<=d[i]-1;j++) change(j,-1);
}
}
if(n==1){
if(d[1]>0) puts("0");
else puts("1");
return 0;
}
else if(n==2){
if((d[1]!=1&&d[1]!=-1)||(d[2]!=1&&d[2]!=-1)) puts("0");
else puts("1");
return 0;
}
for(i=1;i<=n;i++){
if(d[i]==0||d[i]>=n){
puts("0");
return 0;
}
}
for(i=2;i<=n-2;i++) change(i,1);
for(i=2;i<=n-sum-2;i++) change(i,-1);
for(i=1;i<=n-sum-2;i++) change(n-cnt,1);
ans[1]=l=1;
for(i=2;i<=1000;i++){
for(j=1;j<=c[i];j++){
int tmp=0;
for(k=1;k<=l;k++){
ans[k]=ans[k]*i+tmp;
tmp=0;
if(ans[k]>=10) tmp=ans[k]/10,ans[k]=ans[k]%10;
}
while(tmp) ans[++l]=tmp%10,tmp/=10;
}
}
for(i=l;i>=1;i--) printf("%d",ans[i]);
puts("");
return 0;
}