Posted on 2008-08-15 15:58
Hero 阅读(178)
评论(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 out( 0 ) ;
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) ) ;
for( int 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 ;
}