BZOJ 1005: [HNOI2008]明明的烦恼

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

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;
}
Avatar_small
cleaning companies i 说:
2019年9月11日 20:06

Dubai Housekeeping is mostly a soundly supervised cleaning supplier in Dubai which usually understands the initial requirements and additionally culture for the UAE and therefore the region. Our housecleaning services happen to be introduced just by recognizing the need for featuring cleaning high quality and put-together cleaning offerings in Dubai and additionally Abu Dhabi. This staff really are carefully chose, well groomed and additionally excellently competent. Staff paid members are put-together in leagues and methodically trained relating to modern cleaning exactly how deliver superior quality consistent housecleaning services for Dubai and additionally Abu Dhabi.

Avatar_small
rapidity news 说:
2019年11月12日 02:04

sensible diet usually means eating the ideal proportions and also servings of each food. If you ever eat primarily protein foodstuff but almost no fruits and also vegetables, your food intake isn't sensible. Following the perfect portion sizes of each food set: 3-4 oz (unit card deck sized) with protein.

Avatar_small
wanamassa reale stat 说:
2020年3月18日 17:35

Essentially the most important investments off our life is a Real Real estate investment and will probably be for sure essentially the most appreciated possessions that any of us will include on your entire lifetime.

Avatar_small
north bama real esta 说:
2020年3月18日 17:35

An authentic estate vocation is both equally popular between individuals as that career isn't going to require almost any degree or maybe certificate. There are various Men in addition to women real estate brokers out there who definitely are doing that job often full-time or maybe part-time.

Avatar_small
atlanta black busine 说:
2020年3月18日 17:36

Small business list usually are compiled in addition to updated regular monthly with help of sources like yellow websites directories, business plastic cards, annual studies, business in addition to industry internet directories, and cellular phone verification.

Avatar_small
freeze business rate 说:
2020年3月18日 17:36

World-wide-web Buisness, internet marketing and blogs all head out together very well. In unique, you can certainly add word links on your blog threads. These inbound links will capture your webpage viewer through which your sales page for ones affiliate method.

Avatar_small
shawcor success 说:
2020年3月18日 17:37

When you hate standing up the next day and about to work for other people, then you'll be ready an home based internet business. People accomplish this for a variety of reasons, like being while using the kids or merely a transform of way of living.

Avatar_small
monthly maid service 说:
2020年4月27日 20:41

Though oahu is the bride who does the major planning with the wedding wedding party, it can be included inside the maid regarding honor obligations. It will be more of your supportive function, as the particular maid regarding honor need to actually control and implement regardless of bride ideas. Most brides to be also find the maid of honor's opinions on a regular basis. You need to guide the particular bridesmaids although practicing the wedding ceremony ceremony with all the bride.

Avatar_small
construction paintin 说:
2020年4月27日 20:42

Majorly, you must discuss using your family along with decide your color inclination. One ought to know what they are trying to find, before in search of help via professional artists. Once these are sure today, they should seek out available property painters out there. Before allowing them to visit anyone, you need to visit his or her offices to receive their portfolios.

Avatar_small
maids in dubai 说:
2021年6月06日 19:39

At this point, if people implement all of the tips as i have said above, it will be easy to hold on to a fresh room and allow your house an innovative look. On top of that, if you would like any succeeding help, subsequently call House maid Agency Dubai. Professionals include immense know-how about computers the clean-up process together with cleaning instruments. Thus, you can certainly retain your relief by getting expert aid.


登录 *


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