首页 > 代码库 > [HNOI2008]明明的烦恼

[HNOI2008]明明的烦恼

2024-09-26 18:23:02   212人阅读

1005: [HNOI2008]明明的烦恼

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 5090  Solved: 1986
[Submit][Status][Discuss]

Description

　　自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?

Input

　　第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

　　一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

3
1
-1
-1

Sample Output

2

HINT

 

　　两棵树分别为1-2-3;1-3-2

 

prufer序列+压位高精+组合数

黄学长无可挑剔题解 http://hzwer.com/3272.html

吓得我都不敢写了（其实是懒）

#include<cstdio>#define N 1001#define mod 1000000using namespace std;int a[N],tot,m,n;int prime[N],sum[N],cnt,ans[N];bool v[N];void pre_prime(){    for(int i=2;i<N;i++)    {        if(!v[i]) prime[++cnt]=i;        for(int j=1;j<=cnt;j++)        {            if(prime[j]*i>N-1) break;            v[prime[j]*i]=true;            if(i%prime[j]==0) break;        }    }}void apart(int k,int w){    int tmp=k;    for(int j=1;j<=cnt;j++)    {         k=tmp;         while(k)         {             sum[j]+=w*k/prime[j];             k/=prime[j];         }    }}void mul(int x){    for(int i=1;i<=ans[0];i++) ans[i]*=x;    for(int i=1;i<=ans[0];i++)     {        ans[i+1]+=ans[i]/mod;        ans[i]%=mod;    }    while(ans[ans[0]+1])     {         ans[0]++;        ans[ans[0]+1]=ans[0]/mod;        ans[0]%=mod;     }}void out(){    printf("%d",ans[ans[0]]);    for(int i=ans[0]-1;i;i--) printf("%06d",ans[i]);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)     {        scanf("%d",&a[i]);        if(a[i]==-1) m++;        else tot+=--a[i];    }    if(tot>n-2) { printf("0"); return 0; }    pre_prime();    apart(n-2,1);    apart(n-2-tot,-1);    for(int i=1;i<=n;i++) if(a[i]) apart(a[i],-1);    //for(int i=1;i<=cnt;i++) printf("%d\n",sum[i]);    ans[0]=ans[1]=1;    for(int i=1;i<=cnt;i++)  for(int j=1;j<=sum[i];j++)  mul(prime[i]);    for(int i=1;i<=n-2-tot;i++) mul(m);    out();}

 

 

[HNOI2008]明明的烦恼


联系
我们