[고밀도] [codevs 1145] 하노이 쌍 탑 문제

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 2000
#define base 10000
using namespace std;
int n;
struct Bign
{
	int c[maxn],len,sign;
	//    
	Bign(){memset(c,0,sizeof(c)),len = 1,sign = 0;}
	//    
	void Zero()
	{
		while(len > 1 && c[len] == 0)len--;
		if(len == 1 && c[len] == 0)sign = 0;		
	} 
	//     
	void Write(char *s)
	{
		int k = 1,l = strlen(s);
		for(int i = l - 1;i >= 0;i--)
		{
			c[len] += (s[i] - '0') * k;
			k *= 10;
			if(k == base)
			{
				k = 1;
				len++;
			}
		}
	}
	void Read()
	{
		char s[maxn] = {0};
		scanf("%s",s);
		Write(s);
	}
	//  
	void Print()
	{
		if(sign)printf("-");
		printf("%d",c[len]);
		for(int i = len - 1;i >= 1;i--)printf("%04d",c[i]);
		printf("
");
	} 
	//   =    ，         
	Bign operator = (int a)
	{
		char s[100];
		sprintf(s,"%d",a);
		Write(s);
		return *this;//this        ，          
	} 
	//   <    
	bool operator < (const Bign &a)const
	{
		if(len != a.len)return len < a.len;
		for(int i = len;i >= 1;i--)
		{
			if(c[i] != a.c[i])return c[i] < a.c[i];
		}
		return 0;
	}
	bool operator > (const Bign &a)const
	{
		return a < *this;
	}
	bool operator <= (const Bign &a)const
	{
		return !(a < *this);
	}
	bool operator >= (const Bign &a)const
	{
		return !(*this < a);
	}
	bool operator != (const Bign &a)const
	{
		return a < *this || *this < a;
	}
	bool operator == (const Bign &a)const
	{
		return !(a < *this) && !(*this < a);
	}
	bool operator == (const int &a)const
	{
		Bign b;b = a;
		return *this == b;
	}

	//   +    
	Bign operator + (const Bign &a)
	{
		Bign r;
		r.len = max(len,a.len) + 1;
		for(int i = 1;i <= r.len;i++)
		{
			r.c[i] += c[i] + a.c[i];
			r.c[i + 1] += r.c[i] / base;
			r.c[i] %= base; 
		}
		r.Zero();
		return r;
	} 
	Bign operator + (const int &a)
	{
		Bign b;b = a;
		return *this + b;
	}
	//   -    
	Bign operator - (const Bign &a)
	{
		Bign b,c;// b - c
		b = *this;
		c = a;
		if(c > b)
		{
			swap(b,c);
			b.sign = 1;
		}
		for(int i = 1;i <= b.len;i++)
		{
			b.c[i] -= c.c[i];
			if(b.c[i] < 0)
			{
				b.c[i] += base;
				b.c[i + 1]--;
			}
		}
		b.Zero();
		return b;
	} 
	Bign operator - (const int &a)
	{
		Bign b;b = a;
		return *this - b;
	}
	//   *     
	Bign operator * (const Bign &a)
	{
		Bign r;
		r.len = len + a.len + 2;
		for(int i = 1;i <= len;i++)
		{
			for(int j = 1;j <= a.len;j++)
			{
				r.c[i + j - 1] += c[i] * a.c[j];
			}
		} 
		for(int i = 1;i <= r.len;i++)
		{
			r.c[i + 1] += r.c[i] / base;
			r.c[i] %= base;
		}
		r.Zero();
		return r;
	} 
	Bign operator * (const int &a)
	{
		Bign b;b = a;
		return *this * b;
	}
	//   /     
	Bign operator / (const Bign &b)
	{
		Bign r,t,a;
		a = b;
		//if(a == 0)return r;
		r.len = len;
		for(int i = len;i >= 1;i--)
		{
			t = t * base + c[i];
			int div,ll = 0,rr = base;
			while(ll <= rr)
			{
				int mid = (ll + rr) / 2;
				Bign k = a * mid;
				if(k > t)rr = mid - 1;
				else
				{
					ll = mid + 1;	
					div = mid; 
				} 
			}
			r.c[i] = div;
			t = t - a * div;
		}
		r.Zero();
		return r; 
	}
	Bign operator / (const int &a)
	{
		Bign b;b = a;
		return *this / b;
	}
	//   %    
	Bign operator % (const Bign &a)
	{
		return *this - *this / a * a;
	}
	Bign operator % (const int &a)
	{
		Bign b;b = a;
		return *this % b;
	}
};

int main()
{
	scanf("%d",&n);
	Bign ans;
	ans =1;
	for(int i=1;i<=n+1;i++)
	ans=ans+ans;
	ans=ans-2;
	ans.Print();
	return 0;
}