bzoj1211 [HNOI2004]树的计数（prufer序列+组合数学+计数）

对于一颗n个点的无根树，我们可以得到唯一的prufer序列，长度为n-2。
每一个prufer序列也都唯一对应了一颗无根树。
每一个点x在prufer序列中的出现次数为d[x]-1,d[x]为x点的度数。

此题给定每个点的度数，求一共有多少种不同的树，也就是求有多少种不同的prufer序列，满足每个数x出现了d[x]-1次。
我们应用组合数学的知识得到答案就是 (n−2)!∏ni=1(d[i]−1) 。

注意判非法，直接乘会爆ll，所以我们可以分解质因数来算。
复杂度 O(n2)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 200
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int n,d[N],sum,cnt[N],num[N];
ll ans=1;
inline void gao(int xx){
    int x=xx;
    for(int i=2;i*i<=xx;++i)
        while(x%i==0) num[i]+=cnt[xx],x/=i;
    if(x!=1) num[x]+=cnt[xx];
}
inline ll ksm(ll x,int k){
    ll res=1;for(;k;k>>=1,x*=x) if(k&1) res*=x;return res;
}
int main(){
// freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i){
        d[i]=read(),sum+=d[i];if(!d[i]&&n!=1){puts("0");return 0;}
    }if(sum!=n*2-2){puts("0");return 0;}
    for(int i=2;i<=n-2;++i) cnt[i]++;
    for(int i=1;i<=n;++i)
        for(int j=2;j<=d[i]-1;++j) cnt[j]--;
    for(int i=2;i<=n-2;++i) gao(i);
    for(int i=2;i<=n-2;++i) ans*=ksm(i,num[i]);
    printf("%lld\n",ans);
    return 0;
}