[文章目录]
Description
给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?给出第i个节点的度数Di,如果对度数不要求,则输入-1，n<=1000
Prufer序列：对于一个树，每次找到编号最小的叶子节点删掉，将与其相连的点记入序列，直到剩下两个节点，所形成的序列。
性质：
1.可以得到一个长度为n-2的序列，并且每个数出现的次数等于该点在树上的度数-1。
2.树和prufer序列一一对应。
那么这道题，只需要统计对应可能的Prufer序列个数就好了，对于已知度数的点，组合的方案数为
对于未知度数的点，假设有k个，那么答案乘以
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=100000000;
int n,d[1010];
int pri[1010],yz[1010],num[1010],cnt;
bool v[1010];
inline void initialize()
{
yz[1]=1;
for(int i=2;i<=n;++i)
{
if(!v[i]) pri[++cnt]=i,yz[i]=i;
for(int j=1;i*pri[j]<=n&&j<=cnt;++j)
{
v[i*pri[j]]=1;
yz[i*pri[j]]=pri[j];
if(i%pri[j]==0) break;
}
}
}
inline void work(int x)
{
int now;
for(int i=2;i<=x;++i)
{
now=i;
while(now!=1)
{
num[yz[now]]--;
now/=yz[now];
}
}
}
struct precision
{
ll w[400]; int cnt;
precision(){memset(w,0,sizeof w); cnt=0;}
precision operator * (const int z)
{
precision re;
for(int i=1;i<=cnt;++i) re.w[i]=w[i]*z;
re.cnt=cnt; ll t=0,tmp;
for(int i=1;i<=cnt;++i)
{
tmp=re.w[i];
re.w[i]=(tmp+t)%mod;
t=(tmp+t)/mod;
}
while(t) re.w[++re.cnt]=t%mod,t/=mod;
return re;
}
precision operator = (int x)
{
precision re;
while(x) re.w[++re.cnt]=x%mod,x/=mod;
return (*this)=re,re;
}
void print()
{
printf("%lld",w[cnt]);
for(int i=cnt-1;i>0;--i) printf("%08lld",w[i]);
}
}ans;
int main()
{
scanf("%d",&n);
initialize();
for(int i=1;i<=n;++i) scanf("%d",d+i);
int now;
for(int i=2;i<=n-2;++i)
{
now=i;
while(now!=1)
{
num[yz[now]]++;
now/=yz[now];
}
}
int sum=n-2,tim=0;
for(int i=1;i<=n;++i)
{
if(d[i]==-1){ tim++; continue;}
sum-=(d[i]-1); work(d[i]-1);
}
work(sum);
precision ans; ans=1;
for(int i=1;i<=cnt;++i)
{
while(num[pri[i]])
{
ans=ans*pri[i];
num[pri[i]]--;
}
}
while(sum) ans=ans*tim,sum--;
ans.print();
return 0;
}