1005: [HNOI2008]明明的烦恼
题目：
题解：
毒瘤题啊天~
其实思考的过程还是比较简单的。。。
首先当然还是要了解好的基本性质啦
那么和1211大体一致，主要还是利用组合数学：
首先我们把度数和-n记录为sum，那么根据prufer序列，序列的元素个数就是n-2
那就是要在n-2个位置中选sum个，然后就是分别根据度数要求算每个元素在sum个位置中的方案，然后乘起来。最后还要乘上没有度数要求的元素的方案数就...ok啦
思考两分钟...代码两小时...太菜啦！！！！
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #define qread(x) x=read() 7 using namespace std; 8 inline int read() 9 {10 int f=1,x=0;char ch;11 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13 return f*x;14 }15 struct node16 {17 int len,a[11000];18 node(){memset(a,0,sizeof(a));}19 }no,n1;20 void chengfa(int x)21 {22 int i;23 for(i=1;i<=no.len;i++)no.a[i]=no.a[i]*x;24 for(i=1;i<=no.len;i++)25 {26 no.a[i+1]+=no.a[i]/10;27 no.a[i]%=10;28 }29 i=no.len;30 while(no.a[i+1]>0)31 {32 i++;33 no.a[i+1]+=no.a[i]/10;34 no.a[i]%=10;35 }36 no.len=i;37 while(no.a[no.len]==0 && no.len>1)no.len--;38 }39 bool pd(int x)40 {41 if(x<2)return false;42 double t=sqrt(double(x+1));43 for(int i=2;i<=t;i++)44 if(x%i==0)45 return false;46 return true;47 }48 int n,d[1100],pr[1100],s[1100];49 int main()50 {51 scanf("%d",&n);int cnt=0,sum=0;52 if(n==1){qread(d[1]);if(d[1]){printf("0\n");return 0;}else {printf("1\n");return 0;}}53 for(int i=1;i<=n;i++)54 {55 qread(d[i]);56 if(d[i]==0){printf("0\n");}57 if(d[i]==-1)cnt++;58 else d[i]-=1,sum+=d[i];59 }60 if(sum>n-2){printf("0\n");return 0;}61 if(sum 0)80 {81 for(int k=2;k<=d[i];k++)82 {83 int x=k;84 for(int j=1;j<=len;j++)85 while(x%pr[j]==0 && x!=0)86 s[j]--,x/=pr[j];87 }88 }89 no.a[1]=1;no.len=1;90 for(int i=1;i<=len;i++)91 while(s[i]--)92 chengfa(pr[i]);93 for(int i=1;i<=n-2-sum;i++)chengfa(cnt);94 for(int i=no.len;i>=1;i--)95 printf("%d",no.a[i]);96 printf("\n");97 return 0;98 }