【BZOJ 1005】明らかな悩み

【題解を見ないと一生思い出せないシリーズの一つ】
ツリーのpruferコードは、具体的な内容は黄先輩のブログをご覧ください.
http://hzwer.com/3272.html
小技を実現するには、大域的に配列して答えを覚えるのです.各素因数の回数は最後に合わせて乗ります.bign*intだけです.
＜del＞しかし、データ規模が小さいので、何の最適化もしていません.

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define maxn 1005
void _read(int &x)
{
	x=0; char ch=getchar(); bool flag=false;
	while(ch<'0' || ch>'9'){if(ch=='-')flag=1; ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	if(flag)x=-x;
	return ;
}
int n,cnt,sum,d[maxn],pre_cnt,pre[2*maxn],a[2*maxn],b[2*maxn]; 
bool v[2*maxn],wrong;
void getpre(int T)//           
{
	memset(v,0,sizeof(v));
	for(int i=2;i<=T;i++)if(!v[i])
	{
		pre[++pre_cnt]=i;
		for(int j=i;j*i<=T;j++)v[j*i]=1;
	}
	return ;
}
void Init()
{
	wrong=false;
	_read(n); 
	sum=0;cnt=0;
	for(int i=1;i<=n;i++)_read(d[i]);
	
	for(int i=1;i<=n;i++)if(d[i]==0){wrong=true;return;}
	for(int i=1;i<=n;i++)if(d[i]!=-1){cnt++,sum+=(d[i]-1);}
	getpre(2000);
	return ;
}
void fj(int now)//           
{
	int t=0;
	memset(b,0,sizeof(b));
	if(now==1)return ;
	for(int i=1;i<=pre_cnt;i++)
	{
		t=pre[i];
		while(t<=now){b[i]+=now/t; t=t*pre[i];}
	}
	return ;
}
void getC(int x,int y)
{
	fj(y);for(int i=1;i<=pre_cnt;i++)a[i]+=b[i];
	fj(x);for(int i=1;i<=pre_cnt;i++)a[i]-=b[i];
	fj(y-x);for(int i=1;i<=pre_cnt;i++)a[i]-=b[i];
	return ;
}
void getA()
{
	fj(sum);for(int i=1;i<=pre_cnt;i++)a[i]+=b[i];
	for(int j=1;j<=n;j++)if(d[j]-1>0)
	{
		fj(d[j]-1);
		for(int i=1;i<=pre_cnt;i++)a[i]-=b[i];
	}
	return ;
}
void getPower()
{
	memset(b,0,sizeof(b));
	if(cnt<n)
	{
		int t=n-cnt;
		for(int i=1;i<=pre_cnt;i++)
		{
			if(t<=1)break;
			while(t%pre[i]==0 && t>0){b[i]++; t=t/pre[i];}			
		}
		for(int i=1;i<=pre_cnt;i++)b[i]*=(n-2-sum);
	}
	for(int i=1;i<=pre_cnt;i++)a[i]+=b[i];
	return ;
}
struct bign
{
	int a[4005],n;
	bign()
	{
		memset(a,0,sizeof(a)); n=1; a[1]=1;
	}
	friend bign operator *(bign x,int y)
	{
		bign b;
		b.n=x.n+5;
		for(int i=1;i<=b.n;i++)b.a[i]=x.a[i]*y;
		for(int i=1;i<=b.n;i++)if(b.a[i]>=10){b.a[i+1]+=b.a[i]/10; b.a[i]=b.a[i]%10;}
		while(b.a[b.n]==0)b.n--;
		return b;
	}
}ans;
void Output()
{
	
	for(int i=1;i<=pre_cnt;i++)
	{
		for(int j=1;j<=a[i];j++)ans=ans*pre[i];
	}
	for(int i=ans.n;i>=1;i--)putchar(ans.a[i]+'0');
	putchar('
');
	return ;
}
void work()
{
	memset(a,0,sizeof(a));//a              
	//      
	getC(sum,n-2);
	//       
	getA(); 
	//      
	getPower();
	Output();
	return ; 
}
int main()
{
	freopen("in.txt","r",stdin);
	Init();
	if(n==1)
	{
		if(d[1]==0)printf("1
");
		else printf("0
");
		return 0;
	}
	if(sum<=n-2 && wrong==false)work();
	else printf("0
");
	return 0;
}