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+3],pd[N+3],a[N+3][N+3],mp[N+3],n,d[N+3],ans[N+3];
void init()
{
for (int i=2;i<=N;i++) {
if (!pd[i]) prime[++prime[0]]=i,mp[i]=prime[0];
for (int j=1;j<=prime[0];j++) {
if (prime[j]*i>N) break;
            pd[prime[j]*i]=1;
if (i%prime[j]==0) break;
        }
    }
}
void calc(int x,int a[N])
{
for (int i=1;prime[i]*prime[i]<=x;i++)
if (x%prime[i]==0) 
while (x%prime[i]==0) x/=prime[i],a[i]++;
if (x>1) a[mp[x]]++;
}
bool check()
{
if (n==1&&d[1]!=0) return true;
int t=0; int tot=0;
for (int i=1;i<=n;i++) {
if (!d[i]) t++;
     tot+=d[i]-1;
    }
if (n!=1&&t) return true;
if (tot!=n-2) return true; 
return false;
}
int main()
{
    freopen("ctree.in","r",stdin);
    freopen("ctree.out","w",stdout);
scanf("%d",&n);
int mx=n-2;init();
for (int i=1;i<=n;i++) scanf("%d",&d[i]),mx=max(mx,d[i]-1);
if (check()) {
printf("0\n");
return 0;
    }
for (int i=1;i<=mx;i++) calc(i,a[i]);
for (int i=1;i<=mx;i++) 
for (int j=1;j<=prime[0];j++) a[i][j]+=a[i-1][j];
for (int i=1;i<=prime[0];i++) ans[i]=a[n-2][i];
for (int i=1;i<=n;i++)
for (int j=1;j<=prime[0];j++) ans[j]-=a[d[i]-1][j];
    LL sum=1;
for (int j=1;j<=prime[0];j++)
if (ans[j])
while (ans[j]) sum*=(LL)prime[j],ans[j]--;
printf("%lld\n",sum);
}