1012.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//DP方程同 1009
#include <iostream>
#include <string>

using namespace std;

const int HPlen = 3005;
const int Base  = 10000;
class HP; typedef const HP& crHP;

class HP
{
public:
	int len;	//len 要比实际长度多1
	int d[HPlen + 1];
	HP(int x = 0)
	{
		memset(d, 0, sizeof(d));
		for( len = 1; x; x/=Base) d[len++] = x%Base;
		if( len != 1 )len--;
	}
	HP(crHP A) { *this = A; }
	
	void print()
	{
		printf( "%d" , d[ len ] );
		for( int i = len - 1; i > 0; i-- )printf("%04d", d[i]);
		printf("\n");
	}	
	
	void operator = (int);
	
	HP operator + ( const int & );
	HP operator + ( crHP );
	
	HP operator * (const int &);
	HP operator * ( crHP );
};

void HP::operator = ( int x )
{
   memset( d, 0, sizeof(d) );
   for( len = 1; x; x/=Base) d[len++] = x%Base;
   if(len != 1)len--;
}

/*=============================readIn====================================*/
const int Size_s = 1000;
void readHP( HP& A )
{
   char s[ Size_s ]; int ls, t, k,p,i;
   scanf("%s",s); ls=strlen(s);
   p=A.len=(ls+3)/4;
   for( k=A.len*4-ls, t=i=0;  i<ls;  ++i )
   {
      t=t*10+s[i]-'0';
      if( ++k==4 ) A.d[ p-- ]=t, k=t=0;
   }
}

/*=============================ADD====================================*/
HP HP::operator + ( crHP B )
{
   HP C( *this );  int i;
   if( C.len < B.len ) C.len = B.len ;
   for( i=1; i<=C.len; ++i )
   {
      C.d[i] += B.d[i] ;
      if( C.d[i]>=Base ) C.d[i]-=Base , ++C.d[i+1];
   }
   if( C.d[ i ] ) C.len = i ;
   return C;
}
HP HP::operator + ( const int & b )
{
	HP B(b);
	HP C = (*this) + B;
	return C;
}

/*=============================Mult====================================*/

HP HP::operator * ( crHP B )
{
   HP C;
   int i,j, t, di;
   for( i=1; i<= len; C.d[ i+j-1 ]+=t, ++i )
      for( di=d[i], t=0, j=1; j<= B.len; ++j )
         t += C.d[ i+j-1 ] + di*B.d[j] ,
         C.d[ i+j-1 ] = t % Base  ,  t /= Base ;
         
   for( C.len=len+B.len;  C.len>0 && !C.d[ C.len ];  C.len-- );
   return C;
}

HP HP::operator * ( const int & b )
{   HP B(b); return (*this)*B ;   }


int main()
{
	int k, n;
	HP f,f1,f2;
	cin >> n >> k;
	f2 = k-1,f1 = k*(k-1);f = f1;
	for(int i = 3; i <= n; i++ )
	{
		f = (f1 + f2)*(k-1);
		f2 = f1;
		f1 = f;
	}
	f.print();
	return 0;
}