[BZOJ1211][HNOI2004]树的计数（prufer序列+数学相关）

题目描述

传送门

题目大意：一个n个节点的树，给出每一个点的度，问满足要求的生成树有多少个

题解

树的prufer序列裸题
答案应该是 (n−2)!∏i(di−1)! ，相当于是一个有重复元素的排列问题
但是我被无解的情况坑了挺久的…其实也不难
特判n=1的情况； ∑di=n−2 ； di≥1

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
#define N 155

int n;
int d[N],cnt[N];
LL ans;

int main()
{
    scanf("%d",&n);
    if (n==1)
    {
        int x;scanf("%d",&x);
        if (!x) puts("1");
        else puts("0");
        return 0;
    }
    int sum=0;
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&d[i]);
        if (!d[i])
        {
            puts("0");
            return 0;
        }
        sum+=d[i]-1;
    }
    if (sum!=n-2)
    {
        puts("0");
        return 0;
    }
    for (int i=2;i<=n-2;++i)
    {
        int x=i;
        for (int j=2;j*j<=x&&x>1;++j)
            while (x%j==0) ++cnt[j],x/=j;
        if (x>1) ++cnt[x];
    }
    for (int i=1;i<=n;++i)
        for (int j=2;j<d[i];++j)
        {
            int x=j;
            for (int k=2;k*k<=x&&x>1;++k)
                while (x%k==0) --cnt[k],x/=k;
            if (x>1) --cnt[x];
        }
    ans=1;
    for (int i=1;i<=n;++i)
        while (cnt[i]) ans=ans*(LL)i,--cnt[i];
    printf("%lld\n",ans);
}