记录编号	141089	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2008]明明的烦恼	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-11-29 00:56:51	内存使用	0.29 MiB

#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstdlib>
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 1010;
struct BigN{
	#define base 1000000
	#define maxl 600
	int A[maxl], len;
	BigN(){len = 1, A[0] = 0;}
	BigN &operator *= (int x){
		int i, mor = 0;
		for(i = 0;i < len || mor;++i){
			if(i < len)mor += A[i] * x;
			A[i] = mor % base;
			mor /= base;
		}
		if(i > len)len = i;
		return *this;
	}
}ans;
int N, S = 0, A[maxn], Acnt = 0, Bcnt = 0, prime[maxn], pcnt = 0;
inline void euler(){
	int i, j;
	bool not_p[maxn] = {0};
	for(i = 2;i <= N;++i){
		if(!not_p[i])prime[pcnt++] = i;
		for(j = 0;j < pcnt;++j){
			if(prime[j] * i > N)break;
			not_p[prime[j]*i] = 1;
			if(i % prime[j] == 0)break;
		}
	}
}
inline void init(){
	getd(N);
	if(N == 0){putchar('0');exit(0);}
	int i, d;
	if(N == 1){
		getd(d);
		if(d == -1 || !d)putchar('1');
		else putchar('0');
		exit(0);
	}
	for(i = 1;i <= N;++i){
		getd(d);
		if(d == 0){putchar('0');exit(0);}
		if(d == -1) ++Bcnt;
		else {
			A[Acnt++] = d - 1;
			S += d - 1;
		}
	}
	if((S > N-2) || (S < N-2 && !Bcnt)){
		putchar('0');
		exit(0);
	}
	A[Acnt++] = N - 2 - S;
	S = N - 2;
	euler();
}
int powcnt[maxn] = {0};
inline void res(int n){
	int i, j;
	for(i = 0;i < pcnt;++i){
		j = prime[i];
		while(j <= n){
			powcnt[i] -= n / j;
			if(powcnt[i] < 0){printf("0");exit(0);}
			j *= prime[i];
		}
	}
}
inline void work(){
	int i, j = Acnt - 1, p;
	ans.A[0] = 1;
	for(i = 1;i <= A[j];++i)
		ans *= Bcnt;
	for(i = 0;i < pcnt;++i){
		p = prime[i];
		while(p <= S){
			powcnt[i] += S / p;
			p *= prime[i];
		}
	}
	for(i = 0;i < Acnt;++i)
		res(A[i]);
	for(i = 0;i < pcnt;++i){
		for(j = 1;j <= powcnt[i];++j)
			ans *= prime[i];
	}
	i = ans.len - 1;
	int *Ans = ans.A;
	printf("%d", Ans[i]);
	while(i--)
		printf("%06d", Ans[i]);
}
int main(){
	freopen("bzoj_1005.in", "r", stdin);
	freopen("bzoj_1005.out", "w", stdout);
	init();
	work();
	return 0;
}