记录编号	272475	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 数列	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2016-06-16 21:46:21	内存使用	0.32 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=110;
struct ExtInt{
	int a[maxn],len;
	ExtInt(){
		memset(a,0,sizeof(a));
		len=1;
	}
	void clear(){
		memset(a,0,sizeof(a));
		len=1;
	}
	int operator [](int x){
		return a[x];
	}
	void Print(){
		for(int i=len;i>=1;i--)
			printf("%d",a[i]);
		printf("\n");	
	}
}ans,F;



ExtInt operator /(ExtInt a,int x){
	ExtInt ret;
	for(int i=a.len,tot=0;i>=1;i--){
		tot=tot*10+a[i];
		ret.a[i]=tot/x;
		tot%=x;
	}
	ret.len=a.len;
	while(!ret[ret.len]&&ret.len>1)ret.len-=1;
	return ret;	
}

ExtInt operator +(ExtInt a,int x){
	ExtInt ret;
	for(int i=1,in=0;i<=a.len||in;i++){
		ret.a[i]=a[i]+in+x%10;x/=10;
		in=ret.a[i]/10;ret.a[i]%=10;
	}
	ret.len=a.len+1;
	while(!ret[ret.len]&&ret.len>1)ret.len-=1;
	return ret;
}
ExtInt operator +(ExtInt a,ExtInt x){
	ExtInt ret;
	for(int i=1,in=0;i<=max(a.len,x.len)||in;i++){
		ret.a[i]=in+a[i]+x.a[i];
		in=ret.a[i]/10;ret.a[i]%=10;
	}
	ret.len=max(a.len,x.len)+1;
	while(!ret[ret.len]&&ret.len>1)ret.len-=1;
	return ret;
}

ExtInt p,q;
void Solve(ExtInt x){
	if(x[1]==1&&x.len==1){
		p=x;q.clear();
		return;
	}
	Solve((x+1)/2);
	if(x[1]&1)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+1);
		int len=strlen(s+1);
		for(int i=1;i<=len;i++)
			F.a[len-i+1]=s[i]-'0';
		F.len=len;	
		Solve(F);
		p.Print();	
	}
	return 0;
}