好的我把标准版过了。。。
设$ r_i$为$i$的度数
首先，我们设 $ sum = Sigma r_i-1$，$ tot $ 为所有能够确定度数的点
所以我们有
$ C ^ {sum} _{n-2} * frac{sum!}{Pi(r_i-1)!} *(n-tot)^{n-2-sum} $
$C ^ {sum} _{n-2}$ 表示从n-2个位置中选出sum个（因为他们肯定出现在$ Prufer$序列里）
$ frac{sum!}{Pi(r_i-1)!}$是多重集的排列
$(n-tot)^{n-2-sum} $ 是指拿剩下的n-tot个点，填在$Prufer$ 剩下的位置中
原式经化简为
$ frac{(n-2)!}{(n-2-sum)!*Pi(r_i-1)!}*(n-tot)^{n-2-sum}$
所以把他们分解质因数扔进去就好了
然后要用高精（第一次压位qwq）
#include<cstdio> #include<iostream> #include<cstring> #define R register int using namespace std; const int B=10000,N=1010; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } struct Int { int sz,dat[2010]; Int() {sz=0; memset(dat,0,sizeof(dat));} inline void init(int vl) { sz=0; while(vl) ++sz,dat[sz]=vl%B,vl/=B; } inline void print() { printf("%d",dat[sz]); for(R i=sz-1;i;--i) printf("%04d",dat[i]); } }; Int operator *(Int a,int b) { Int c; R lst=a.sz; for(R i=1;i<=lst;++i) c.dat[i]=a.dat[i]*b; for(R i=1;i<=lst;++i) c.dat[i+1]+=c.dat[i]/B,c.dat[i]%=B; while(c.dat[lst+1]) ++lst,c.dat[lst+1]+=c.dat[lst]/B,c.dat[lst]%=B; c.sz=lst; return c; } Int ans; int n,sum,tot; int r[N],cnt[N]; inline void add(int x,int vl) { for(R i=2;i*i<=x;++i) while(x%i==0) x/=i,cnt[i]+=vl; if(x>1) cnt[x]+=vl; } signed main() { //freopen("1.in","r",stdin); freopen("out.out","w",stdout); n=g(); for(R i=1;i<=n;++i) { r[i]=g(); if(r[i]==-1) continue; ++tot,sum+=r[i]-1; } if(sum>n-2) {printf("0 "); return 0;} for(R i=n-2;i;--i) add(i,1); for(R i=n-2-sum;i;--i) add(i,-1); for(R i=1;i<=n;++i) { if(r[i]==-1) continue; for(R j=1;j<r[i];++j) add(j,-1); } for(R i=1;i<=n-2-sum;++i) add(n-tot,1); ans.init(1); for(R i=1;i<=n;++i) for(R j=1;j<=cnt[i];++j) ans=ans*i; ans.print(); putchar(' '); }
2019.05.16