# URAL1013[K-based numbers. Version 3]

URAL1009URAL1012的加强版，需要高精再加优化。

sum{f[i],0<=i<=N/2}
f[i]=C(N-i,i)*(K-1)^(N-i)
f[i-1]=C(N-i+1,i-1)*(K-1)^(N-i+1)
f[i]/f[i-1]=C(N-i,i)/C(N-i+1,i-1)/(K-1)
=((N-i)!/(N-i+1)!) * ((N-i*2+2)!/(N-i*2)!) * ((i-1)!/i!) / (K-1)
=1/(N-i+1)         * (N-i*2+2)*(N+i*2+1)   * 1/i           / (K-1)
=((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))
f[i]=f[i-1]*((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-13

DESCRIPTION:

\$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#include <iomanip>

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class BigNumber

{

static const int BASE=10000;

vector<int> d;

public:

BigNumber(int value=0)

:d(1,value)

{

//assert(value<BASE);

}

friend BigNumber operator+(const BigNumber& a,const BigNumber& b)

{

BigNumber c;

c.d.resize(a.d.size()>b.d.size()?a.d.size():b.d.size());

int over=0;

for (int i=0;i<c.d.size();i++)

if (i<a.d.size()&&i<b.d.size())

{

c.d[i]=(a.d[i]+b.d[i]+over)%BASE;

over=(a.d[i]+b.d[i]+over)/BASE;

}

else if (i<a.d.size())

{

c.d[i]=(a.d[i]+over)%BASE;

over=(a.d[i]+over)/BASE;

}

else if (i<b.d.size())

{

c.d[i]=(b.d[i]+over)%BASE;

over=(b.d[i]+over)/BASE;

}

if (over) c.d.push_back(over);

return c;

}

BigNumber& operator*=(int mul)

{

int over=0;

for (int i=0;i<d.size();i++)

{

int old=d[i];

d[i]=(old*mul+over)%BASE;

over=(old*mul+over)/BASE;

}

if (over) d.push_back(over);

return *this;

}

BigNumber& operator/=(int div)

{

int rest=0;

for (int i=d.size()-1;i>=0;i–)

{

int old=d[i];

d[i]=(rest*BASE+old)/div;

rest=(rest*BASE+old)%div;

}

if (d[d.size()-1]==0) d.resize(d.size()-1);

return *this;

}

void print()

{

cout<<d[d.size()-1];

for (int i=d.size()-11;i>=0;i–)

cout<<std::setfill(‘0’)<<std::setw(4)<<d[i]<<std::setw(1)<<std::setfill(‘ ‘);

cout<<endl;

}

};

class Application

{

int N,K;

public:

Application()

{

cin>>N>>K;

}

int run()

{

//sum{(N-i)!/(((N-i*2)!)*(i!))*((K-1)^(N-i)), 0<=i<=N/2}

//f[i]=C(N-i,i)*(K-1)^(N-i)

//f[i-1]=C(N-i+1,i-1)*(K-1)^(N-i+1)

//f[i]/f[i-1]=C(N-i,i)/C(N-i+1,i-1)/(K-1)

//           =((N-i)!/(N-i+1)!) * ((N-i*2+2)!/(N-i*2)!) * ((i-1)!/i!) / (K-1)

//           =1/(N-i+1)         * (N-i*2+2)*(N+i*2+1)   * 1/i           / (K-1)

//           =((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))

//f[i]=f[i-1]*((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))

BigNumber get(1);

for (int i=0;i*2<=N;i++)

{

if (i==0)

for (int j=1;j<=N;j++)

get*=K-1;

else

{

get*=(N-i*2+2);

get*=(N-i*2+1);

get/=(N-i+1);

get/=(i);

get/=K-1;

}

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}