记录编号	176817	评测结果	AAAAAAAAAA
题目名称	[FJOI 2007] 轮状病毒	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-08-09 21:30:14	内存使用	0.32 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

struct BIGNUM{
	string s;
	friend BIGNUM operator +(BIGNUM a,BIGNUM b){
		string s1=a.s;
		string s2=b.s;
		if(s1.length()>s2.length() ){
      	   string ts=s1;
      	   s1=s2;
      	   s2=ts;
    	}
   	 	int i;
   	    int j; 
   	    for(i=s2.length()-1,j=s1.length()-1;j>=0;j--,i--){
      	  	int index=i;        
      	  	int sum=(s2[i]-'0')+(s1[j]-'0');
      	  	while(sum>=10){
       	      	s2[index]=(char)(sum%10+'0');
      	      	if(index<=0){
       	         	s2="1"+s2;
       	         	i++;
       	 		    index++;
       	  	       break;
       	   	    }
       	    	  index--;
           	   sum=(s2[index]-'0')+1;
          	}
    		s2[index]=(char)(sum%10+'0');
    	}
		BIGNUM aa;
		aa.s=s2; 
    	return aa;		
	}
	friend BIGNUM operator - (BIGNUM A,BIGNUM B){
			string s1=A.s;
			string s2=B.s;
    		int l1=s1.size();
    		int l2=s2.size();
    		int a[241]={0},b[241]={0},c[241]={0};
    		if(((s1<s2)&&(l1==l2))||(l1<l2)){
      	       cout<<'-';
     		   string s3=s1;
     		   s1=s2;
               s2=s3;
            }
   			else
        		if(s1==s2){
        			BIGNUM k;
        			k.s="0";
        			return k;
			}
			int m=s1.size();
    		for(int i=0;i<m;++i)
    		{
        		a[m-i-1]=s1[i]-'0';
    		}
    		int n=s2.size();
    		for(int i=0;i<n;++i){
        		b[n-i-1]=s2[i]-'0';
    		}
    		int len = 0;
    		len=(m>n?m:n);
    		for(int i=0;i<len;++i)
    		{
        		if(a[i]<b[i])
        		{
            		--a[i+1];
            		a[i]+=10;
        		}
        		c[i]=a[i]-b[i];
    		}
    		for(int i=len-1;i>0;i--)
    		{
	    		if(c[i]==0)
	        		len--;
	    		else
	        		break;
    		}
    		string ANS;
    		for(int i=len-1;i>=0;i--)
    		{
        		ANS+=(char)(c[i]+48);
    		}
    		BIGNUM kk;
			kk.s=ANS;
		return kk;
	}
};
int n;
int main(){
	freopen("bzoj_1002.in","r",stdin);
	freopen("bzoj_1002.out","w",stdout);
	cin>>n;
	if(n==1){
		cout<<1;
		return 0;
	}
	BIGNUM zhong;
	BIGNUM temp; temp.s="1";
	BIGNUM ans; ans.s="5";
	BIGNUM two ; two.s="2";
	for(int i=3;i<=n;i++){
		zhong=ans;
		ans=(ans+ans)+(ans-temp)+two;
		temp=zhong;
	}
	cout<<ans.s;
	return 0;
}