BZOJ1211: [HNOI2004]树的计数(prufer序列)

// luogu-judger-enable-o2
#include<cstdio>
#define int long long 
using namespace std;
const int MAXN = 10005;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-')f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int inder[MAXN], N, sum = 0;
int js[MAXN];
main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    #endif
    N = read();
    js[0] = js[1] = 1;
    for(int i = 1; i <= 150; i++) js[i] = js[i-1] * i;
    for(int i = 1; i <= N; i++) {
        inder[i] = read(); sum += inder[i] - 1;
        if(inder[i] == 0 && N != 1) {printf("0");return 0;}
    }
    if(sum != N - 2) {printf("0");return 0;}
    int Now = 1, times = 1;
    for(int i = 1; i <= N - 2; i++) {
        Now *= i;    
        if(times > N) break;
        if(Now % js[ inder[times] - 1 ] == 0) Now /= js[ inder[times] - 1], times++;
    }
    printf("%lld",Now);
    return 0;
}