我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

URAL——1012——(递推+高精度)

Posted on 2008-08-15 15:58 Hero 阅读(185) 评论(0)  编辑 收藏 引用 所属分类: 代码如诗--ACM
/*
ID: wangzha4
LANG: C++
TASK: palsquare
*/
//JUDGE_ID: 65448BI

//f[1] = 10 ;--特殊
//f[2] = 9 * 10 ;
//f[3] = 9 * ( 9 + 9 *10 ) ;
//f[n] = 9*(f[n-2] + f[n-1]) ;
//f[n]表示以第n个数字开头最多能构建满足条件的解的个数

#include 
<iostream>
using namespace std ;

#define unllong unsigned long long 
#define unint unsigned int
#define printline  printf( "\n" ) 
typedef 
long long llong ;
//const double PI = 2.0 * acos( 0.0 ) ;

const int Base=1000000000;
const int Capacity=500;
const int INF = 1000000 ;
const int size = 155 ;

struct BigInt{
    
int Len;
    
int Data[Capacity];
    BigInt():Len(
0){}
    BigInt(
const BigInt &V):Len(V.Len){memcpy(Data,V.Data,Len*sizeof*Data);}
    BigInt(
int V):Len(0){for(;V>0;V/=Base) Data[Len++]=V%Base;}
    BigInt 
&operator=(const BigInt &V){Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return *this;}
    
int &operator[](int Index){return Data[Index];}
    
int operator[](int Index)const{return Data[Index];}
};

int compare(const BigInt &A,const BigInt &B){
    
if(A.Len!=B.Len) return A.Len>B.Len ? 1:-1;
    
int i;
    
for(i=A.Len-1;i>=0 && A[i]==B[i];i--);
    
if(i<0)return 0;
    
return A[i]>B[i] ? 1:-1;
}

BigInt 
operator+(const BigInt &A,const BigInt &B){
    
int i,Carry(0);
    BigInt R;
    
for(i=0;i<A.Len||i<B.Len||Carry>0;i++){
        
if(i<A.Len) Carry+=A[i];
        
if(i<B.Len) Carry+=B[i];;
        R[i]
=Carry%Base;
        Carry
/=Base;
    }
    R.Len
=i;
    
return R;
}

BigInt 
operator-(const BigInt &A,const BigInt &B){
    
int i,Carry(0);
    BigInt R;
    R.Len
=A.Len;
    
for(i=0;i<R.Len;i++){
        R[i]
=A[i]-Carry;
        
if(i<B.Len) R[i]-=B[i];
        
if(R[i]<0) Carry=1,R[i]+=Base;
        
else Carry=0;
    }
    
while(R.Len>0&&R[R.Len-1]==0) R.Len--;
    
return R;
}

BigInt 
operator*(const BigInt &A,const int &B){
    
int i;
    llong Carry(
0);
    BigInt R;
    
for(i=0;i<A.Len||Carry>0;i++){
        
if(i<A.Len) Carry+=llong(A[i])*B;
        R[i]
=Carry%Base;
        Carry
/=Base;
    }
    R.Len
=i;
    
return R;
}

istream 
&operator>>(istream &In,BigInt &V){
    
char Ch;
    
for(V=0;In>>Ch;){
        V
=V*10+(Ch-'0');
        
if(In.peek()<=' 'break;
    }
    
return In;
}

ostream 
&operator<<(ostream &Out,const BigInt &V){
    
int i;
    Out
<<(V.Len==0 ? 0:V[V.Len-1]);
    
for(i=V.Len-2;i>=0;i--for(int j=Base/10;j>0;j/=10) Out<<V[i]/j%10;
    
return Out;
}


int inn, ink ;

const BigInt Bint( 1 ) ;
BigInt 
out0 )  ;
BigInt a( 
0 ) ;
BigInt bint[
2000] ;

void process()
{
    bint[
1= Bint * ink ;
    bint[
2= Bint * ( (ink-1)*(ink) ) ;
    bint[
3= Bint * ( (ink-1)*((ink-1)+(ink-1)*ink) ) ;

    
forint i=4; i<=inn; i++ )
    {
        bint[i] 
= ( bint[i-2+ bint[i-1] )*(ink-1) ;
    }
}


void output()
{
    cout 
<< bint[inn] << endl ;
}


int main()
{
    
while( cin >> inn >> ink )
    {
        
//input() ;

        process() ;

        output() ;
    }

    
return 0 ;

}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理