标签：数学，高精度
Description
自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?
Input
第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output
一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input
3
1
-1
-1
Sample Output
2
HINT
两棵树分别为1-2-3;1-3-2
分析：针对N==1和存在Di==0的情况可以先进行特判
正解关于树的prufer编码，可以参考这篇博客
这样就可以用prufer编码存储树了
对于M个无限制的节点，存储方案为M^(n-2-tot)
其余限制的节点，有C（tot,n-2）种方案
之后就转化为高精度除法的问题（今年初赛的坑高精度除法…）
其实可以将除法转化为乘法的问题，质因数分解，累程求ans，高精度过程中使用了压位技巧
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1006,mod=1e4;
int d[maxn],num[maxn],pri[maxn],ans[maxn],l=1,n,m,tot,x,cnt;
inline bool jud(int x){
rep(i,2,sqrt(x))if(x%i==0)return 0;
return 1;
}
inline void mul(int x){
rep(i,1,l)ans[i]*=x;
rep(i,1,l){
ans[i+1]+=ans[i]/mod;
ans[i]%=mod;
}
while(ans[l+1]>0){
l++;
ans[l+1]=ans[l]/mod;
ans[l]%=mod;
}
}//高精度压位
void solve(int a,int f){
rep(k,1,a){
int x=k;
rep(i,1,cnt){
if(x<=1)break;
while(x%pri[i]==0){num[i]+=f;x/=pri[i];}
}
}
}//num[i]打上标记，等最后一起累乘
int main()
{
rep(i,2,1000)
if(jud(i))pri[++cnt]=i;//统计质数的个数
ans[1]=1;
n=read();
if(n==1){
x=read();
if(!x)printf("1");
else printf("0");
return 0;
}//特判N==1的情况
rep(i,1,n){
d[i]=read();
if(!d[i]){printf("0");return 0;}
if(d[i]==-1)m++;
else{d[i]--;tot+=d[i];}
}
if(tot>n-2){printf("0");return 0;}
solve(n-2,1);
solve(n-2-tot,-1);
rep(i,1,n)
if(d[i])solve(d[i],-1);
rep(i,1,cnt)
while(num[i]--)mul(pri[i]);
rep(i,1,n-2-tot)mul(m);
dep(i,l,1)if(i==l)printf("%d",ans[i]);else printf("%04d",ans[i]);
return 0;
}
