UPD: 这个题不需要高精乘高精

Prufer序列

有个叫prufer序列的科技，两周前刚见过：洛谷 P4981

大体就是一个prufer序列可以唯一确定一棵树，一棵树也有他唯一的prufer序列。

如果树有 $n$ 个点，序列长度就为 $n-2$，值域为 $[1,n]$。

Prufer序列的求法

1.找到编号最小的叶子，把他去掉，然后把他的父亲加入prufer序列，直到还剩下1的个点，所以prufer序列的长度是$n-2$。

然后发现：

如果一个点的度为d，他会在prufer序列里面出现d-1次。

所以先放度数确定的，一个一个求组合数就行。然后在放度数随意的，使用快速幂。

思路代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d[1005];
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>d[i];
		--d[i];
	}
	int cnt=0,sum=0,ans=0;
	for(int i=1;i<=n;++i){
		if(d[i]==-2) cnt++;
		else sum+=d[i];
	}
	int tt=n-2;
	for(int i=1;i<=n;++i){
		if(d[i]!=-2&&tt>0){
			ans=ans*C(tt,d[i])
			tt-=d[i];
		}
	}
	for(int i=1;i<=n-2-sum;++i){
		ans=ans*cnt;
	}
	cout<<ans<<"\n";
	return 0;
}

最后别忘了高精度。

这是原题：洛谷P2290，他不用高精度。

代码仅供参考

#include<bits/stdc++.h>
#define int long long

using namespace std;
int n,d[1005];
struct node{
	int len,a[2005];
}as;
int v[1005],p[1005],tot,c[1005];
void init(){
	for(int i=2;i<=1000;++i){
		if(v[i])continue;
		for(int j=i;j<=1000/i;++j){
			v[i*j]=1;
		}
	}
	for(int i=2;i<=1000;++i){
		if(v[i]==0){
			p[++tot]=i;
		}
	}
}
void mul(int b){
	for(int j=1;j<=as.len;++j){
		as.a[j]*=b;
	}
	for(int j=1;j<as.len;++j){
		if(as.a[j]>9999999){
			as.a[j+1]+=as.a[j]/10000000;
			as.a[j]%=10000000;
		}
	}
	while(as.a[as.len]>9999999){
		as.a[as.len+1]+=as.a[as.len]/10000000;
		as.a[as.len]%=10000000;
		++as.len;
	}
}
void C(int n,int m){
	memset(c,0,sizeof c);
	for(int i=n-m+1;i<=n;++i){
		int t=i;
		for(int j=1;j<=tot;++j){
			while(t%p[j]==0){
				++c[j];
				t/=p[j];
			}
		}
	}
	for(int i=1;i<=m;++i){
		int t=i;
		for(int j=1;j<=tot;++j){
			while(t%p[j]==0){
				--c[j];
				t/=p[j];
			}
		}
	}
	for(int i=1;i<=tot;++i){
		for(int j=1;j<=c[i];++j){
			mul(p[i]);
		}
	}
}
signed main(){
	as.a[1]=as.len=1;
	cin>>n;
	init();
	for(int i=1;i<=n;++i){
		cin>>d[i];--d[i];
	}
	int cnt=0,sum=0;
	for(int i=1;i<=n;++i){
		if(d[i]==-2) cnt++;
		else sum+=d[i];
	}
	for(int i=1;i<=n-2-sum;++i){
		mul(cnt);
	}
	int tt=n-2;
	for(int i=1;i<=n;++i){
		if(d[i]!=-2&&tt>0){
			C(tt,d[i]);
			tt-=d[i];
		}
	
	}
	cout<<as.a[as.len];
	for(int i=as.len-1;i>=1;--i){
		int ans[10]={0},j=0;
		while(as.a[i]){
			ans[++j]=as.a[i]%10,as.a[i]/=10;
		}
		for(int k=7;k>=1;--k){
			cout<<ans[k];
		}
	}
	return 0;
}

对了，大家写完代码别忘了删freopen