记录编号	289794	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]麦森数	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2016-08-05 15:48:29	内存使用	0.26 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long LL;
const LL mod=10000;
LL max(LL a,LL b){
	return a>b?a:b;
}
struct bignum{
	LL num[130];
	bignum(){
		memset(num,0,sizeof(num));
	}
	bignum operator*(bignum b){
		bignum c;
		c.num[0]=max(num[0],b.num[0]);
		for(int i=1;i<=num[0];++i){
			for(int j=1;j<=b.num[0]&&i+j-1<=125;++j){
				c.num[i+j-1]+=num[i]*b.num[j];
			}
		}
		for(int i=1;i<=c.num[0];++i){
			if(c.num[i]>=mod){
				c.num[i+1]+=c.num[i]/mod;
				c.num[i]%=mod;
				if(i==c.num[0]&&c.num[0]<125)c.num[0]++;
			}
		}
		return c;
	}
};
bignum ans,a;
void QuickPow(int p){
	ans.num[0]=1;ans.num[1]=1;
	a.num[0]=1;a.num[1]=2;
	for(;p;p>>=1,a=a*a){
		if(p&1){
			ans=ans*a;
		}
	}
}
int main(){
	freopen("mason.in","r",stdin);
	freopen("mason.out","w",stdout);
	int p;scanf("%d",&p);
	printf("%d\n",(int)ceil(log(2)/log(10)*p));
	QuickPow(p);
	ans.num[1]--;
	for(int i=125;i>=1;--i){
		printf("%04lld",ans.num[i]);
		if(i%25==1)printf("\n");
	}
	fclose(stdin);fclose(stdout);
	return 0;
}