Accepted/4312K/454MS

poj1737.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct Int{
	long long a[200];
	Int()
	{
		memset(a,0,sizeof(a));
	}
	Int(long long _a)
	{
		memset(a,0,sizeof(a));
		a[0]=_a;
		for (int i=0;i<=198;i++)
		{
			a[i+1]+=a[i]/10000;
			a[i]%=10000;
		}
	}
	Int operator + (Int b)
	{
		Int ret(0);
		for (int i=0;i<=199;i++)
			ret.a[i]=a[i]+b.a[i];
		for (int i=0;i<=198;i++)
		{
			ret.a[i+1]+=ret.a[i]/10000;
			ret.a[i]%=10000;
		}
		return ret;
	}
	Int operator * (Int b)
	{
		Int ret;
		for (int i=0;i<=100;i++)
			for (int j=0;j<=100;j++)
				ret.a[i+j]+=a[i]*b.a[j];
		return ret;
	}
	void Print(const char add[])
	{
		int w=190;
		while (a[w]==0)
			w--;
		printf("%lld",a[w]);
		for (int i=w-1;i>=0;i--)
			printf("%04lld",a[i]);
		printf("%s",add);
	}
};
int main()
{
	Int dp[60];
	Int c[51][51];
	c[0][0]=Int(1);
	for (int i=1;i<=50;i++)
		c[i][0]=c[i][i]=Int(1);
	for (int i=2;i<=50;i++)
		for (int j=1;j<i;j++)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	dp[1]=dp[0]=Int(1);
	for (int i=2;i<=50;i++)
	{
		dp[i]=Int(0);
		for (int j=1;j<i;j++)
			dp[i]=dp[i]+dp[j]*Int((1LL<<j)-1)*dp[i-j]*c[i-2][j-1];
	}
	int n=0;
	while ((~scanf("%d",&n)) && n)
	{
		dp[n].Print("\n");
	}
	return 0;
}