BZOJ1211树的计数

裸的prufer结论。

给个小链接prufer序列 ，里面有一个性质4就是本题答案，严谨证明可以上网找一找，如果从多组组合角度理解也可以。

剩下的就是特判，n==1时，du==0，1个，du！=0，废了。有du==0，废了。度数和大于（还是不等于来着？）2*(n-1)，废了。拿到67分……。

接着就是求那个式子了，我有一套O（n）拆一个阶乘的理论。那这个就是O（n^2）了呗。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

#define ll long long

using namespace std;

ll ans=,n,du[],sum,prime[],prime_num;

bool v[];

ll read(){

    ll sum=;int f=;char x=getchar();

    while(x<''||x>''){

        if(x=='-') f=-;

        x=getchar();

    }while(x>=''&&x<=''){

        sum=sum*+x-'';

        x=getchar();

    }return sum*f;

}

void doprime(int x){

    for(int i=;i<=x;i++){

        if(!v[i]) prime[++prime_num]=i;

        for(int j=;j<=prime_num&&i*prime[j]<=x;j++){

            v[i*prime[j]]=;

            if(i%prime[j]==) break;

        }

    }

}

ll qpow(ll x,ll k){

    ll ans=;

    for(;k;k>>=,x=x*x)

        if(k&) ans=ans*x;

    return ans;

}

int main(){

    n=read();

    if(n==){

        du[]=read();

        if(!du[]) puts("");

        else puts("");

        return ;

    }

    for(int i=;i<=n;i++){

        du[i]=read();

        if(!du[i]){

            puts("");

            return ;

        }

        sum+=du[i];

    }

    if(sum!=*(n-)){

        puts("");

        return ;

    }

    doprime(n);

    for(int i=;i<=prime_num;i++){

        int s=;

        for(int j=n-;j/=prime[i];) s+=j;

        for(int j=;j<=n;j++)

            for(int k=du[j]-;k/=prime[i];) s-=k;

        ans=ans*qpow(prime[i],s);

    }printf("%lld",ans);

    return ;

}