[bzoj1211][prufer序列]树的计数

本文主要是介绍[bzoj1211][prufer序列]树的计数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

一个有n个结点的树，设它的结点分别为v1, v2, …,
vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …,
dn，编程需要输出满足d(vi)=di的树的个数。

Input

第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。

Output

输出满足条件的树有多少棵。

Sample Input

4
2 1 2 1

Sample Output

2

题解

新东西,prufer序列
1：一个prufer序列唯一对应一个无根树
2：n个节点的无根树唯一对应了一个n-2的prufer序列
3：一个节点的度数-1等于他在这个prufer序列中出现的次数，反之亦然
4：n个节点的无根树共有n^(n-2)个
这道题只是用了第三个性质，第四个其实没有用到。。
可以想到，给出的度数d[i]-1的sigma就是这个prufer序列的长度。那么不考虑重复的情况下，这个prufer序列的全排列就是(n-2)!
考虑重复，一个节点在这个prufer序列中出现的是d[i]-1次，那么应该对于每个节点，都除以d[i]-1，d[i]=1的情况不需要处理
记得特判n=1，度数为0这些情况。
虽然说结果不会爆long long，但是中间会爆，所以质因数分解吧

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL pri[150];int t;
LL n,d[210],sum;
LL s[150],pr[150];
bool pd(int x)
{if(x==1)return false;int t=int(double(sqrt(x+1)));for(int i=2;i<=t;i++)if(x%i==0)return false;return true;
}
void get_pri(LL a)
{int p=1;memset(pr,0,sizeof(pr));while(a>1){while(a%pri[p]==0){a/=pri[p];pr[p]++;}p++;if(p>t)break;}
}
int main()
{scanf("%lld",&n);sum=0;for(int i=1;i<=n;i++){scanf("%lld",&d[i]);sum+=d[i]-1;if(n>1 && d[i]==0){printf("0\n");return 0;}}if(n==1 && d[1]!=0){printf("0\n");return 0;}if(sum!=n-2){printf("0\n");return 0;}memset(s,0,sizeof(s));t=0;for(int i=1;i<=150;i++)if(pd(i))pri[++t]=i;for(int i=1;i<=n-2;i++){get_pri(i);for(int i=1;i<=t;i++)s[i]+=pr[i];}for(int i=1;i<=n;i++){if(d[i]==1)continue;get_pri(d[i]-1);for(int i=1;i<=t;i++)s[i]-=pr[i];}LL ans=1;for(int i=1;i<=t;i++){for(int j=1;j<=s[i];j++)ans*=pri[j];}printf("%lld\n",ans);return 0;
}