Prufer 序列

XUER_WANG · 2023-07-17 15:40:53 · 个人记录

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x1=0,x2=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')x2=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x1=x1*10+ch-'0';
        ch=getchar();
    }
    return x1*x2;
}
const int N=155;
int n,ans,sum,a[N],f[N][N];
inline void prufer(){
    for(int i=0;i<=n;i++){
        f[i][0]=1;
        for(int j=1;j<=i;j++){
            f[i][j]=f[i-1][j]+f[i-1][j-1];
        }
    }
}
int main(){
    n=read();
    if(n==1){
        a[1]=read();
        if(!a[1])cout<<"1\n";
        else cout<<"0\n";
        return 0;
    }
    prufer();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(!a[i]){
            cout<<"0\n";
            return 0;
        }
        a[i]--;
        sum+=a[i];
    }
    if(sum!=n-2){
        cout<<"0\n";
        return 0;
    }
    sum=0,ans=1;
    for(int i=1;i<=n;i++){
        ans*=f[n-2-sum][a[i]];
        sum+=a[i];
    }
    cout<<ans<<'\n';
    return 0;
}