BZOJ 1005: [HNOI2008]明明的烦恼

starli posted @ 2016年3月06日 16:02 in 数学 , 290 阅读

prufer数列+高精度

http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html

详细的介绍可以看这篇blog

知道这个之后 只要计算prufer数列的个数就好了

首先将有度数限制的所有点数一下,这些点的度数-1就是在数列中出现的次数,这可以用含有重复元素的排列来解决。剩下来的位置可以用任意一个没有度数限制的点来填,乘法原理一下即可。

注意特判n=1和2的情况。

计算组合数的时候除法除单精度的数即可

#include <cstdio>
#include <algorithm>
using namespace std;
const int MOD=10,N=5010;
struct bigint{int a[N];
	void reset(){for(int i=0;i<N;i++) a[i]=0;a[0]=1;}
	void operator =(int x){
		reset();
		for(;x;x/=MOD,a[0]++) a[a[0]]=x%MOD;
		if(a[0]>1) a[0]--;
	}
	void print(){
		for(int i=a[0];i;i--) putchar(a[i]+'0');
	}
}ans;
int n,s[N],sum,sum2;
bigint operator *(bigint x,int y){
	for(int i=1;i<=x.a[0];i++) x.a[i]*=y;
	for(int i=1;i<x.a[0];i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD;
	for(int& i=x.a[0];x.a[i]>=MOD;i++) x.a[i+1]+=x.a[i]/MOD,x.a[i]%=MOD;
	return x;
}
bigint operator /(bigint x,int y){
	bigint z;int tmp=0;
	z=0;z.a[0]=x.a[0];
	for(int i=x.a[0];i;i--) z.a[i]=(tmp*MOD+x.a[i])/y,tmp=(tmp*MOD+x.a[i])%y;
	for(int &i=z.a[0];!z.a[i] && i;) 
		i--;
		if(!z.a[0]) z.a[0]++;
	return z;
}
int main(){
	scanf("%d",&n);
	if(n==1){
		scanf("%d",&s[1]);	
    		printf(s[1]?"0":"1");
       		return 0;
	}
	for(int i=1;i<=n;i++) {
		scanf("%d",&s[i]),s[i]>=1?sum+=s[i]-1:sum2++;
		if(!s[i]) {printf("0");return 0;}
	}
	if(sum>n-2) {printf("0");return 0;}
	ans=1;
	for(int i=n-2;i>=n-2-sum+1;i--) ans=ans*i;
	for(int i=1;i<=n;i++) if(s[i]>1) for(int j=1;j<=s[i]-1;j++) ans=ans/j;
	for(int i=1;i<=n-2-sum;i++) ans=ans*(sum2);
	ans.print();
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter