prufer序列

[BZOJ1005]明明的烦恼

　　百度题解第一篇简直清晰得飞起，orz

　　懒得写高精度除法，因为结果一定是整数，所以可以分解质因数乱搞

 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("
");
74     return 0;
75 
76 }

View Code

[BZOJ1211]树的计数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define maxp 150
 5 int pri[maxp+5],num[maxp+5],check[maxp+5],pp;
 6 
 7 void getpri(){
 8     for(int i=2;i<=maxp;i++){
 9         if(!check[i])pri[++pp]=i;
10         for(int j=2*i;j<=maxp;j+=i)
11             check[j]=1;
12     }
13 }
14 void cal(int x,int v){
15     for(int i=1;i<=maxp;i++)
16         while(x>1&&x%pri[i]==0){
17             num[i]+=v;
18             x/=pri[i];
19         }
20 }
21 int main(){
22     getpri();
23     int n,x;
24     scanf("%d",&n);
25     if(n==1){
26         scanf("%d",&x);
27         if(!x)puts("1");
28         else puts("0");
29         return 0;
30     }
31     int tot=0;
32     for(int i=1;i<=n;i++){
33         scanf("%d",&x);
34         if(!x){
35             puts("0");
36             return 0;
37         }
38         tot+=x-1;
39         for(int j=1;j<=x-1;j++)
40             cal(j,-1);
41     }
42     if(tot!=n-2){
43         puts("0");
44         return 0;
45     }
46     for(int i=1;i<=n-2;i++)cal(i,1);
47     long long ans=1;
48     for(int i=1;i<=pp;i++)
49         while(num[i]--)ans*=pri[i];
50     printf("%lld
",ans);
51     return 0;
52 }

View Code