Bzoj1005 [hnoi2008]明明的烦恼

Posted by yjjr's blog on February 6, 2018

标签:数学,高精度

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

 

分析:针对N==1和存在Di==0的情况可以先进行特判

正解关于树的prufer编码,可以参考这篇博客

这样就可以用prufer编码存储树了

对于M个无限制的节点,存储方案为M^(n-2-tot)

其余限制的节点,有C(tot,n-2)种方案

之后就转化为高精度除法的问题(今年初赛的坑高精度除法…)

其实可以将除法转化为乘法的问题,质因数分解,累程求ans,高精度过程中使用了压位技巧

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
    LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1006,mod=1e4;
int d[maxn],num[maxn],pri[maxn],ans[maxn],l=1,n,m,tot,x,cnt;
inline bool jud(int x){
	rep(i,2,sqrt(x))if(x%i==0)return 0;
	return 1;
}
inline void mul(int x){
	rep(i,1,l)ans[i]*=x;
	rep(i,1,l){
		ans[i+1]+=ans[i]/mod;
		ans[i]%=mod;
	}
	while(ans[l+1]>0){
		l++;
		ans[l+1]=ans[l]/mod;
		ans[l]%=mod;
	}
}//高精度压位 
void solve(int a,int f){
	rep(k,1,a){
	    int x=k;
		rep(i,1,cnt){
		    if(x<=1)break;
			while(x%pri[i]==0){num[i]+=f;x/=pri[i];}
		}
	}
}//num[i]打上标记,等最后一起累乘 

int main()
{
    rep(i,2,1000)
        if(jud(i))pri[++cnt]=i;//统计质数的个数 
    ans[1]=1;
    n=read();
    if(n==1){
    	x=read();
    	if(!x)printf("1");
    	else printf("0");
    	return 0;
    }//特判N==1的情况 
    rep(i,1,n){
    	d[i]=read();
    	if(!d[i]){printf("0");return 0;}
    	if(d[i]==-1)m++;
    	else{d[i]--;tot+=d[i];}
    }
    if(tot>n-2){printf("0");return 0;}
    solve(n-2,1);
	solve(n-2-tot,-1);
	rep(i,1,n)
	    if(d[i])solve(d[i],-1);
	rep(i,1,cnt)
	    while(num[i]--)mul(pri[i]);
	rep(i,1,n-2-tot)mul(m);
	dep(i,l,1)if(i==l)printf("%d",ans[i]);else printf("%04d",ans[i]);
    return 0;
}
    



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr