BZOJ 1211 树的计数(purfer序列)

首先考虑无解的情况， 根据purfer序列，当dee[i]=0并且n!=1的时候，必然无解。否则为1.

且sum(dee[i]-1)!=n-2也必然无解。

剩下的使用排列组合即可推出公式。需要注意的是题目虽然说最终答案不会超过1e17，但是中间过程可能超。

由于n<=150, 所以sum最多是148. 于是我们可以打出150*150的组合表。实现O(1)计算组合数。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int dee[];

LL cc[][];

void init()

{

    FOR(i,,) {

        cc[i][]=;

        FOR(j,,i) cc[i][j]=cc[i-][j-]+cc[i-][j];

    }

}

int main ()

{

    init();

    int n, sum=;

    LL ans=;

    scanf("%d",&n);

    if (n==) {

        scanf("%d",dee);

        puts(dee[]==?"":"");

        return ;

    }

    FOR(i,,n) {

        scanf("%d",dee+i), --dee[i], sum+=dee[i];

        if (dee[i]<) {puts(""); return ;}

    }

    if (sum!=n-) {puts(""); return ;}

    FOR(i,,n) {

        if (!dee[i]) continue;

        ans*=cc[sum][dee[i]];

        sum-=dee[i];

    }

    printf("%lld\n",ans);

    return ;

}