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 answer(0);

          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;

              }

              answer=answer+get;

          }

          answer.print();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}