1737.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 244 行

#include <stdio.h>
#include <memory.h>
#include <string.h>

class BigInteger
{
	public:
		enum { MAX = 1000 };
		int len;
		char cNum[MAX];
		int sign;

		BigInteger( int s = 0 )
		{
			len = 0;
			sign = ( s < 0 ) ? -1 : 1;
			s *= sign ;

			memset( cNum, 0, sizeof( cNum ) );
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}
		
		}
		
		BigInteger( char* s )
		{
			
			sign = ( s[0] == '-' ) ? -1 : 1;
			
			if( s[0]=='+' || s[0]=='-' ) s++;
			len = strlen( s );
			
			memset( cNum, 0, sizeof( cNum ) );
			for (int i=0; i<len; i++)
			{
				cNum[i] = s[len-i-1] - '0';
			}
		}

		bool no_more_than( BigInteger& b )
		{
			int i;
			if ( len != b.len )
				return len < b.len;
			else for(i = len-1; i && cNum[i]==b.cNum[i] ; i--)
				;
			return cNum[i] <= b.cNum[i];
		}

		bool operator<( BigInteger& b )
		{
			if ( sign != b.sign )
				return sign < b.sign;
			else return ( sign==1 && !b.no_more_than(*this) ) || ( sign==-1 && !no_more_than(b) );
		}

		BigInteger& operator=( int s )
		{
			len = 0;
			sign = ( s < 0 ) ? -1 : 1;

			memset( cNum, 0, sizeof( cNum ) );
			
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}
			return *this;		
		}
		
		BigInteger plus( BigInteger& b )
		{
			BigInteger c;
			int mmax = ( len > b.len ) ? len : b.len;
			int up = 0;
			int i = 0;
			for (i=0; i<mmax; i++)
			{
				c.cNum[i] = cNum[i] + b.cNum[i] + up;
				up = c.cNum[i] / 10;
				c.cNum[i] %= 10;
			}
			if ( up != 0 )
			{
				c.cNum[mmax] = up;
				mmax ++;
			}
			c.len = mmax;
			c.sign = sign;
			return c;
		}
		
		BigInteger minus( BigInteger& b )
		{
			int i;
			BigInteger c;
		
			for(i=0; i<b.len ; i++)
			{
				c.cNum[i] += cNum[i] - b.cNum[i];
				if( c.cNum[i] < 0 )
				{
					c.cNum[i] += 10;
					c.cNum[i+1]--;
				}
			}
			for( ; i<len ; i++)
			{
				c.cNum[i] += cNum[i];
				if( c.cNum[i] < 0 )
				{
					c.cNum[i] += 10;
					c.cNum[i+1]--;
				}
			}
			c.len = len;
			while( c.len && c.cNum[c.len-1]==0 )
				c.len--;
			
			c.sign = sign;
			return c;
		}

		BigInteger operator+( BigInteger& b )
		{
			if ( sign == b.sign )
			{
				return plus ( b );
			}
			else if( no_more_than( b ) )
				return b.minus ( *this );
			else return minus ( b );
		}

		BigInteger operator-( BigInteger& b )
		{
			BigInteger c=b;
			c.sign=-b.sign;
			return operator+(c);
		}

		BigInteger operator*( BigInteger& t )
		{
			BigInteger s;
			int a;
			if( t.len==0 || len==0 )return 0;
			
			s.sign = sign * t.sign;
			
			for(int i=0 ; i<t.len ; i++)
			if( a = t.cNum[i] )
			{
				for(int j=0 ; j<len ; j++)
				{
					s.cNum[i+j] += a*cNum[j];
					if( s.cNum[i+j] >= 10 )
					{
						s.cNum[i+j+1] += s.cNum[i+j] / 10;
						s.cNum[i+j] %= 10;
					}
				}
			}

			for(s.len = len+t.len+2 ; s.cNum[s.len] == 0 ; s.len-- )
				;
			s.len++;
			return s;
		}
		
		int toOut(char *w)
		{
			int l=0;
			if( len && sign==-1 )
				w[l++] = '-';
			for (int i=len - 1; i>=0; i--)
			{
				w[l++] = cNum[i] + '0';
			}

			if( !len ) w[l++] = '0';
			w[l] = '\0';
			return l;
		}
};

/////////////////////////////////////////////////
#include"stdlib.h"
char w[10000];
BigInteger an[60],c[60][60],t[60];
void init()
{
	int i,j;
	for(i=0;i<51;i++)
	{
		c[i][0]=c[i][i]=1;
	}
	for(i=1;i<51;i++)
	for(j=1;j<i;j++)
		c[i][j]=c[i-1][j]+c[i-1][j-1];
}


int main()
{
	int i,j,k;
	init();
	an[1]=1;
	t[0]=1;
	t[1]=1;
	for(i=2;i<=50;i++)
	{
		an[i]=1;
		k=i*(i-1)/2;
		t[i]=1;
		while(k--)
			t[i]=t[i]*BigInteger(2);
		
		an[i]=t[i];
		for(j=1;j<i;j++)
		{
			an[i]=an[i]-c[i-1][j-1]*an[j]*t[i-j];
		}
	}
	while(1)
	{
		scanf("%d",&k);
		
		if(k==0)break;
		an[k].toOut(w);
		
		printf("%s\n",w);
	}
	return 0;
}