bzoj 1211: [HNOI2004]樹的計數 （prufer序列+組合數學）

題目描述

傳送門

題解

ans=(n−2)!∏(di−1)! ,分解因數，上下相消即可。

注意判斷無解的幾種情況

(1) n=1,d[1]!=0

(2) n!=1,d[i]=0

(3) [∑ni=1(di−1)]!=n−2

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 150
#define LL long long 
using namespace std;
int prime[N+],pd[N+],a[N+][N+],mp[N+],n,d[N+],ans[N+];
void init()
{
    for (int i=;i<=N;i++) {
        if (!pd[i]) prime[++prime[]]=i,mp[i]=prime[];
        for (int j=;j<=prime[];j++) {
            if (prime[j]*i>N) break;
            pd[prime[j]*i]=;
            if (i%prime[j]==) break;
        }
    }
}
void calc(int x,int a[N])
{
    for (int i=;prime[i]*prime[i]<=x;i++)
     if (x%prime[i]==) 
      while (x%prime[i]==) x/=prime[i],a[i]++;
    if (x>) a[mp[x]]++;
}
bool check()
{
    if (n==&&d[]!=) return true;
    int t=; int tot=;
    for (int i=;i<=n;i++) {
     if (!d[i]) t++;
     tot+=d[i]-;
    }
    if (n!=&&t) return true;
    if (tot!=n-) return true; 
    return false;
}
int main()
{
    freopen("ctree.in","r",stdin);
    freopen("ctree.out","w",stdout);
    scanf("%d",&n);
    int mx=n-;init();
    for (int i=;i<=n;i++) scanf("%d",&d[i]),mx=max(mx,d[i]-);
    if (check()) {
        printf("0\n");
        return ;
    }
    for (int i=;i<=mx;i++) calc(i,a[i]);
    for (int i=;i<=mx;i++) 
        for (int j=;j<=prime[];j++) a[i][j]+=a[i-][j];
    for (int i=;i<=prime[];i++) ans[i]=a[n-][i];
    for (int i=;i<=n;i++)
     for (int j=;j<=prime[];j++) ans[j]-=a[d[i]-][j];
    LL sum=;
    for (int j=;j<=prime[];j++)
     if (ans[j])
      while (ans[j]) sum*=(LL)prime[j],ans[j]--;
    printf("%lld\n",sum);
}