好玩但没啥用的$prufer$序列。
记$S$为有度数限制的点的集合，$cnt$为不属于$S$的点的数量，$sum=\sum\limits_{i\in S}d(i)-1$。
先把$S$中的点扔到$prufer$序列里，$C_{n-2}^{sum}$选好位置，序列数有$\dfrac{sum!}{\prod\limits_{i\in S}[d(i)-1]!}$种。
再把剩下的$cnt$个点扔进去，也就是剩下的$n-2-sum$个位置，每个位置有$cnt$种取值，即$cnt^{n-2-sum}$。
答案就是$C_{n-2}^{sum}\dfrac{sum!}{\prod\limits_{i\in S}[d(i)-1]!}cnt^{n-2-sum}$。注意判一下无解。
最后就是恶心的高精了。又双叒叕把别人的板子抄了过来
代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define maxn 1005 #define inf 0x3f3f3f3f using namespace std; inline int read(){ int x=0,y=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return y?-x:x; } int d[maxn]; #include <stack> const int N=10000,B=3,base=1000; struct long_long{ private: int len,a[N]; inline void clear(){while(!a[len]&&len>1) --len;} public: long_long(){memset(a,0,sizeof a);len=0;} long_long(int x){memset(a,0,sizeof a);a[len=1]=x;} void print(){ printf("%d",a[len]); for(int i=len-1;i>0;--i) for(int j=base/10;j>0;j/=10) printf("%d",a[i]/j%10); pn; } long_long &operator =(int x){ stack<char> st;string s; if(!x) return *this="0"; while(x){st.push(x%10+'0');x/=10;} while(!st.empty()) s+=st.top(),st.pop(); return *this=s; } long_long &operator =(const string &s){ memset(a,0,sizeof a);len=0; int l=s.length(); for(int i=0;i<=l;++i){ int j=(l-i+(B-1))/B; a[j]=(a[j]<<1)+(a[j]<<3)+(s[i]^48); } len=(l+(B-1))/B; return *this; } long_long operator +(const long_long &x)const{ long_long res;res.len=max(len,x.len);int k=0; for(int i=1;i<=res.len;++i){ res.a[i]=a[i]+x.a[i]+k; k=res.a[i]/base; res.a[i]%=base; } if(k>0) res.a[++res.len]=k; return res; } long_long operator -(const long_long &x)const{ long_long res=*this; for(int i=1;i<=len;++i){ res.a[i]-=x.a[i]; if(res.a[i]<0) --res.a[i+1],res.a[i]+=base; } res.clear(); return res; } long_long operator *(const int &x)const{ long_long res=*this; for(int i=1;i<=len;++i) res.a[i]*=x; for(int i=1;i<=len;++i) res.a[i+1]+=res.a[i]/base,res.a[i]%=base; int &end=res.len; while(res.a[end+1]>0){++end;res.a[end+1]+=res.a[end]/base,res.a[end]%=base;} return res; } long_long operator *(const long_long &x)const{ long_long res;res.len=len+x.len; for(int i=1;i<=len;++i) for(int j=1;j<=x.len;++j){ res.a[i+j-1]+=a[i]*x.a[j]; res.a[i+j]+=res.a[i+j-1]/base; res.a[i+j-1]%=base; } res.clear(); return res; } long_long operator /(const int &x)const{ long_long res;res.len=len;int k=0; for(int i=len;i>0;--i){ k=k*base+a[i]; res.a[i]=k/x; k%=x; } res.clear(); return res; } int operator %(const int &x)const{ int k=0; for(int i=len;i>0;--i){ k=k*base+a[i]; k%=x; } return k; } bool operator <(const long_long &x)const{ if(len==x.len){ int i; for(i=len;a[i]==x.a[i]&&i>1;--i); if(i>=1) return a[i]<x.a[i]; return false; } return len<x.len; } bool operator >(const long_long &x)const{return !(*this<x);} void operator += (const int &x){*this=*this+x;} void operator *= (const int &x){*this=*this*x;} void operator /= (const int &x){*this=*this/x;} }ans=1; int main(){ int n=read(),sum=0,cnt=0; for(register int i=1;i<=n;++i){ d[i]=read(); if(d[i]==-1)++cnt; else if(d[i]==0){puts("0");return 0;} else sum+=d[i]-1; } if(n==1){printf("%d\n",d[1]==0?1:0);return 0;} if(!n||sum>n-2){puts("0");return 0;} for(register int i=n-2-sum+1;i<=n-2;++i)ans*=i; for(register int i=2;i<=sum;++i)ans/=i; for(register int i=2;i<=sum;++i)ans*=i; for(register int i=1;i<=n-2-sum;++i)ans*=cnt; for(register int i=1;i<=n;++i) if(d[i]!=-1)for(register int j=2;j<d[i];++j)ans/=j; ans.print(); }
