bzoj 2656 [Zjoi 2012] 수열 (sequence) (고밀도)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 const int maxn = 105;
 7 const int base = 1e4;
 8 
 9 struct Bign {
10     int len,N[maxn];
11     int& operator[](const int& i){
12         return N[i];
13     }
14     void init() {
15         len=1;
16         memset(N,0,sizeof(N));
17     }
18 };
19 Bign tmp; char s[maxn];
20 void read(Bign& A)
21 {
22     A.init(),tmp.init();
23     scanf("%s",s+1);
24     int i,j;
25     tmp.len=strlen(s+1);
26     for(int i=1;i<=tmp.len;i++)
27         tmp[i]=s[tmp.len+1-i]-'0';
28     A.len=(tmp.len-1)/4 +1;
29     for(i=1;i<=A.len;i++) {
30         for(j=1;j<=4;j++)
31             A[i]=A[i]*10+tmp[(i-1)*4+(5-j)];
32     }
33 }
34 void print(Bign A)
35 {
36     printf("%d",A[A.len]);
37     for(int i=A.len-1;i;i--)
38         printf("%04d",A[i]);
39     puts("");
40 }
41 Bign operator + (Bign A,Bign B)
42 {
43     A.len=max(B.len,A.len);
44     for(int i=1;i<=A.len;i++) {
45         A[i]+=B[i];
46         A[i+1]+=A[i]/base;
47         A[i]%=base;
48     }
49     while(A[A.len+1]) A.len++;
50     return A;
51 }
52 Bign operator + (Bign A,int x)
53 {
54     Bign B; B.init(); B[1]=x;
55     return A+B;
56 }
57 Bign operator / (Bign A,int p)
58 {
59     for(int i=1;i<=A.len;i++) {
60         if(A[i]&1) A[i-1]+=base/p;
61         A[i]/=p;
62     }
63     while(!A[A.len]&&A.len) A.len--;
64     return A;
65 }
66 
67 Bign p,q,n;
68 
69 void F(Bign x)
70 {
71     if(x.len==1 && x[1]==1) {
72         p=x; q.init(); return ;
73     }
74     F((x+1)/2);
75     if(x[1]&1) p=p+q;
76     else q=p+q;
77 }
78 
79 int main()
80 {
81     int T; scanf("%d",&T);
82     while(T--) {
83         p.init(),q.init();
84         read(n);
85         F(n);
86         print(p);
87     }
88     return 0;
89 }