1211: [HNOI2004]树的计数

题目:传送门

题解:

   今天刚学prufer序列,先打几道简单题

   首先我们知道prufer序列和一颗无根树是一一对应的,那么对于任意一个节点,假设这个节点的度数为k,那么在prufer序列里面这个节点就会出现k-1次

   (反过来也同理成立)

   那么具体的原因这里有解释:

   对于任意一个节点在prufer序列里出现一次的话,那么就表示我有一个孩子被删了,那么少了的一次去哪里了呢,因为每次加进去的都是父亲节点,那么少的肯定就是我自己连出去的一条边啊...

  

   知道了这个推论之后,这道题就很简单了:

   题目要求的树必须满足度数的要求,那只要这棵树的prufer序列满足度数要求就ok了啊...

   这样我们就可以用组合数学,直接根据给出的d数组做。

   很容易想到:ans=(n-2)!/(d1-1)!*(d2-1)!....(dn-1)! (如果是入度小于二的话不用计算)

   刚开始傻逼比的打全排列...有重复啊啊啊啊!!!

   最后一点:题目保证方案数不会超过10^17,那long long 肯定没问题啊...可是我们求得是组合,是有除法的(也就是说乘法的时候还是会爆)....ORT那就质因数分解咯...


代码:

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
typedef long long LL;
using namespace std;
int n;
LL d[],pr[];
int s[];
bool pd(LL x)
{
double t=sqrt(double(x+));
for(int i=;i<=t;i++)
if(x%i==)
return false;
return true;
}
LL p_m(LL a,int b)
{
LL ans=;
while(b!=)
{
if(b%==)ans*=a;
b/=;a*=a;
}
return ans;
}
int main()
{
scanf("%d",&n);int sum=;
for(int i=;i<=n;i++){scanf("%d",&d[i]);sum+=d[i];}
if(n== && d[]!=){printf("0\n");return ;}
if(n>)for(int i=;i<=n;i++){if(d[i]==){printf("0\n");return ;}}
if(sum-n!=n-){printf("0\n");return ;}
int len=;
for(LL i=;i<=;i++)if(pd(i)==true)pr[++len]=i;
memset(s,,sizeof(s));
for(int i=;i<=n-;i++)
{
int x=i;
for(int j=;j<=len;j++)
while(x%pr[j]== && x!=)
{s[j]++;x/=pr[j];}
}
for(int i=;i<=n;i++)
for(int k=;k<=d[i]-;k++)
{
int x=k;
for(int j=;j<=len;j++)
while(x%pr[j]== && x!=)
{s[j]--;x/=pr[j];}
}
LL ans=;
for(int i=;i<=;i++)
ans*=p_m(pr[i],s[i]);
printf("%lld\n",ans);
return ;
}
05-11 17:54