[BZOJ1005]明明的烦恼

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 1000000
 4 #define maxp 1000
 5 int len,ans[maxp+5],check[maxp+5],pri[maxp+5],num[maxp+5],pp;
 6 void era(){
 7     for(int i=2;i<=maxp;i++){
 8         if(!check[i])pri[++pp]=i;
 9         for(int j=2*i;j<=maxp;j+=i)
10             check[j]=1;
11     }
12 }
13 void haha(int x,int v){
14     for(int i=1;i<=pp;i++)
15         while(x>1&&!(x%pri[i]))
16             num[i]+=v,x/=pri[i];
17 }
18 void mul(int x){
19     for(int i=1;i<=len;i++)
20         ans[i]*=x;
21     for(int i=1;i<=len;i++){
22         ans[i+1]+=ans[i]/mod;
23         ans[i]%=mod;
24     }
25     while(ans[len+1]>0){
26         len++;
27         ans[len+1]+=ans[len]/mod;
28         ans[len]%=mod;
29     }
30 }
31 int main(){
32     freopen("bzoj_1005.in","r",stdin);
33     freopen("bzoj_1005.out","w",stdout);
34     era();
35     int n,x;
36     scanf("%d",&n);
37     if(n==1){
38         scanf("%d",&x);
39         if(!x||x==-1)puts("1");
40         else puts("0");
41         return 0;
42     }
43     int sum=0,cnt=0;
44     bool flag=false;
45     for(int i=1;i<=n;i++){
46         scanf("%d",&x);
47         if(!x||x>n-1){
48             puts("0");
49             return 0;
50         }
51         if(x!=-1){
52             cnt++,sum+=x-1;
53             for(int j=1;j<=x-1;j++)
54                 haha(j,-1);
55         }
56         else flag=true;
57     }
58     if(sum>n-2||(sum!=n-2&&!flag)){
59         puts("0");
60         return 0;
61     }
62     for(int i=n-2;i>=n-2-sum+1;i--)
63         haha(i,1);
64     for(int i=1;i<=n-2-sum;i++)
65         haha(n-cnt,1);
66     ans[1]=1,len=1;
67     for(int i=1;i<=pp;i++)
68         while(num[i]--)mul(pri[i]);
69     for(int i=len;i>=1;i--){
70         if(i==len)printf("%d",ans[i]);
71         else printf("%06d",ans[i]);
72     }
73     printf("\n");
74     return 0;
75 
76 }