#include<stdio.h>
#define MAXN 1000001
struct mystruct{
	int a[10];
};
void highsum(struct mystruct a,struct mystruct b,struct mystruct &c){
	int i;
	for(i=0;i<=9;i++) c.a[i]=0;
	for(i=1;i<=8;i++){
		c.a[i]+=(a.a[i]+b.a[i])%10;
		c.a[i+1]+=(a.a[i]+b.a[i])/10;
	}
	c.a[9]/=10;
}
int main(){
	long n,i;
	struct mystruct sum[MAXN];
	for(i=0;i<=9;i++){
		sum[0].a[i]=0;
		sum[1].a[i]=0;
	}
	sum[1].a[1]=1;	
	scanf("%d",&n);
	for(i=2;i<=n;i++)
		if(i&1) sum[i]=sum[i-1];
		else highsum(sum[i-1],sum[i/2],sum[i]);//高精度运算sum[i]=sum[i-1]+sum[i/2];
	i=9;
	while(sum[n].a[i]==0) i--;
	while(i>0){
		printf("%d",sum[n].a[i]);
		i--;
	}
	return 0;
}
	为什么会RE？