数学 ZJOI 2012 数列

时间:2024-01-20 20:56:33

数学 ZJOI 2012 数列

数学 ZJOI 2012 数列

数学 ZJOI 2012 数列

 #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
struct ExtInt{
int a[maxn],len;
ExtInt(){
memset(a,,sizeof(a));
len=;
}
void clear(){
memset(a,,sizeof(a));
len=;
}
int operator [](int x){
return a[x];
}
void Print(){
for(int i=len;i>=;i--)
printf("%d",a[i]);
printf("\n");
}
}ans,F; ExtInt operator /(ExtInt a,int x){
ExtInt ret;
for(int i=a.len,tot=;i>=;i--){
tot=tot*+a[i];
ret.a[i]=tot/x;
tot%=x;
}
ret.len=a.len;
while(!ret[ret.len]&&ret.len>)ret.len-=;
return ret;
} ExtInt operator +(ExtInt a,int x){
ExtInt ret;
for(int i=,in=;i<=a.len||in;i++){
ret.a[i]=a[i]+in+x%;x/=;
in=ret.a[i]/;ret.a[i]%=;
}
ret.len=a.len+;
while(!ret[ret.len]&&ret.len>)ret.len-=;
return ret;
}
ExtInt operator +(ExtInt a,ExtInt x){
ExtInt ret;
for(int i=,in=;i<=max(a.len,x.len)||in;i++){
ret.a[i]=in+a[i]+x.a[i];
in=ret.a[i]/;ret.a[i]%=;
}
ret.len=max(a.len,x.len)+;
while(!ret[ret.len]&&ret.len>)ret.len-=;
return ret;
} ExtInt p,q;
void Solve(ExtInt x){
if(x[]==&&x.len==){
p=x;q.clear();
return;
}
Solve((x+)/);
if(x[]&)p=p+q;
else q=p+q;
} char s[maxn];
int main(){
freopen("sequencezj.in","r",stdin);
freopen("sequencezj.out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
scanf("%s",s+);
int len=strlen(s+);
for(int i=;i<=len;i++)
F.a[len-i+]=s[i]-'';
F.len=len;
Solve(F);
p.Print();
}
return ;
}