P2290 [HNOI2004]树的计数

P2290 [HNOI2004]树的计数
prufer序列模板题

#include <iostream>

#include <cstdio>

#include <queue>

#include <algorithm>

#include <cmath>

#include <cstring>

#define inf 2147483647

#define N 1000010

#define p(a) putchar(a)

#define For(i,a,b) for(long long i=a;i<=b;++i)

//by war

//2019.8.26

using namespace std;

long long n,sum,flag,cnt,temp,ans;

long long a[N],prime[N],tot[N];

bool vis[N];

void in(long long &x){

    long long y=;char c=getchar();x=;

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c<=''&&c>=''){ x=(x<<)+(x<<)+c-'';c=getchar();}

    x*=y;

}

void o(long long x){

    if(x<){p('-');x=-x;}

    if(x>)o(x/);

    p(x%+'');

}

void Euler(){

    for(long long i=;i<=;i++){

        if(!vis[i]) prime[++cnt]=i;

        for(long long j=;j<=cnt&&i*prime[j]<=;j++){

            vis[i*prime[j]]=;

            if(i%prime[j]==)

            break;

        }

    }

}

long long ksm(long long a,long long b){

    long long r=;

    while(b>){

        if(b&) r*=a;

        a*=a;

        b>>=;

    }

    return r;

}

signed main(){

    in(n);Euler();

    For(i,,n){

        in(a[i]),sum+=a[i]-;

        if(!a[i]) flag=;

    }

    if(n==&&flag){

        o(); return ;

    }

    if(sum!=n-||flag){

        o(); return ;

    }

    For(i,,n-){

        temp=i;

        For(j,,cnt)

            while(temp%prime[j]==){

                tot[prime[j]]++;

                temp/=prime[j];

            }

    }

    For(i,,n)

        For(j,,a[i]-){

            temp=j;

            For(k,,cnt)

                while(temp%prime[k]==){

                    tot[prime[k]]--;

                    temp/=prime[k];

                }

        }

    ans=;

    For(i,,cnt)

        ans*=ksm(prime[i],tot[prime[i]]);

    o(ans);

    return ;

}