洛谷P2290 [HNOI2004]树的计数
bzoj1211 [HNOI2004]树的计数
Description
一个有\(n\)个结点的树，设它的结点分别为\(v_1,v_2,\cdots, v_n\)，已知第\(i\)个结点\(v_i\)的度数为\(d_i\)
问满足这样的条件的不同的树有多少棵。
Input
第一行是一个正整数\(n\)，表示树有\(n\)个结点。第二行有\(n\)个数，第\(i\)个数表示\(d_i\)，即树的第\(i\)个结点的度数。其中\(1\le n\le 150\)，输入数据保证满足条件的树不超过\(10^{17}\)个。
Output
输出满足条件的树有多少棵。
可以说是个模板题
prufer 编码，这里只给结论，证明去这里看
我不想复制一遍了
注意一下以下说的“种”和“个”是不同的
由于 prufer 编码的一些性质，其实问题求的就是，总共\(n-2\)个元素，其中有\(n\)种不同元素，每种元素有\(d_i-1\)个，的排列数
所以，如果\(\sum_{i+1}^nd_i-1\neq n-2\)或者\(d_i=0\)则无解，不过要特判\(n=1\)的情况
如何证明在那个链接里都有
首先如果没有这个每种元素多少个的条件，那么\(n-2\)个元素的排列数就是\((n-2)!\)
然后要去重，因为对于每一种元素，这\(d_i-1\)个元素无论怎么变换顺序都是算一种，所以当然要除以\((d_i-1)!\)
那么答案就是：
\[\frac{(n-2)!}{\prod_{i=1}^n d_i-1}
\]
\]
但是题目保证的是最后结果不大于\(10^{17}\)，所以中间值可能会爆\(long long\)
那么我们采取分解质因数的方法，最后再乘起来
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n;
int prime[155],notprime[155];
inline void get_prime(){
for(reg int i=2;i<=n;i++){
if(notprime[i]) continue;
prime[++prime[0]]=i;
for(reg int j=i+i;j<=n;j+=i) notprime[j]=1;
}
}
int num[155],d[155];
inline void mul(int x,int k){
for(reg int i=1;i<=prime[0];i++)
while(!(x%prime[i])) num[i]+=k,x/=prime[i];
}
int main(){
n=read();
if(n==1){
d[1]=read();
return std::puts(d[1]?"0":"1"),0;
}
get_prime();
int sum=0;
for(reg int i=1;i<=n;i++){
sum+=d[i]=read()-1;
if(d[i]==-1) return std::puts("0"),0;
}
if(sum!=n-2) return std::puts("0"),0;
for(reg int i=1;i<=n-2;i++) mul(i,1);
for(reg int i=1;i<=n;i++)
for(reg int j=1;j<=d[i];j++) mul(j,-1);
LL ans=1;
for(reg int i=1;i<=prime[0];i++)
for(reg int j=1;j<=num[i];j++) ans*=prime[i];
std::printf("%lld",ans);
return 0;
}