学步园

题目大意:给你n个点，给你每个点的度数（-1代表谁便是多少），问你有多少种树满足条件  n<=1000

这题一看觉得很神，根本不会写，只会写10的暴力

想了一下，还是没有一点思路，于是就只要搜题解了、、、

这题要用到prufer序列（不知道的自行百度），这种序列是与树一一对应的

而且有个很好的性质，那就是每个点的度数在序列中出现的次数加1

于是这题就很水了，就是一道数学裸题了 不过还要打高精度啊，不想打高精度…除法的可以先把相同的质因子抵消掉就可以了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1011;
struct bign{
	static const int maxlen=800,limit=10000,width=4;
	int len,bit[maxlen];
	int& operator[](int p){return bit[p];}
	void clearbit(){memset(bit,0,sizeof(bit));}
	void delete0(){while(!bit[len-1]&&len>1)--len;}
	bign(int p=0){*this=p;}
	bign& operator=(int p){
		clearbit();len=p?0:1;
		for (;p;p/=limit)bit[len++]=p%limit;
		return *this;
	}
	bign& operator*=(bign b){
		bign a=*this;clearbit();len=a.len+b.len;
		for (int i=0;i<a.len;++i)
			for (int j=0;j<b.len;++j){int tmp=i+j;bit[tmp]+=a[i]*b[j];bit[tmp+1]+=bit[tmp]/limit;bit[tmp]%=limit;}
		delete0();return *this;
	}
};
void write(bign a){
	printf("%d",a.bit[a.len-1]);
	for (int i=a.len-2;i>=0;--i)printf("%04d",a.bit[i]);//4 is width
}
void writeln(bign a){write(a);puts("");}

int n,tot,sum,dsum,d[maxn],s[maxn],N;
void init(){
	scanf("%d",&n); tot=sum=dsum=0;
	for (int i=1;i<=n;++i){
		scanf("%d",d+i); --d[i];
		if (d[i]!=-2) sum+=d[i],d[++dsum]=d[i]; else ++tot;
	}
}
void power(bign &ans,int x,int s){
	static bign tmp; if (!s) return ans=1,void();
	for (tmp=x,ans=1;s;s>>=1,tmp*=tmp) if (s&1) ans*=tmp;
}
bign ans,tmp;
void ins(int x,int add){
	for (int i=2;i*i<=x;++i) if (x%i==0)
		while (x%i==0) s[i]+=add,x/=i;
	if (x!=1) s[x]+=add;
}
void addfact(int x,int add){for (int i=1;i<=x;++i) ins(i,add);}
void work(){
	N=n; n-=2; if (sum>n || (!tot && sum!=n)) return puts("0"),void();
	sum=n-sum; addfact(n,1);
	for (int i=1;i<=dsum;++i) addfact(d[i],-1);
	addfact(sum,-1); ins(tot,sum);
	ans=1; for (int i=1;i<=N;++i){
		power(tmp,i,s[i]); ans*=tmp;
	}
	writeln(ans);
}
int main(){
	init();
	work();
	return 0;
}