Boleyn Su's Blog

水题。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#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 Application

{

      static const int SUM=10000;

      int aN,bN;

      vector<int> a,b;

      public:

      Application()

      {

                   cin>>aN;

                   a.resize(aN);

                   for (int i=0;i<aN;i++) cin>>a[i];

                   cin>>bN;

                   b.resize(bN);

                   for (int i=0;i<bN;i++) cin>>b[i];

      }

      int run()

      {

          bool have=false;

          for (int i=0,j=0;i<aN;i++)

          {

              while (a[i]+b[j]>SUM) j++;

              if (a[i]+b[j]==SUM) have=true;

          }

          cout<<(char*)(have?“YES”:“NO”)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，不过C++的要自己背一下PI的值，貌似URAL不能用<cmath>中的M_PI。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::deque;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cmath>

//using std::M_PI;

#define M_PI (3.141592653589793238462643383279f) //哈哈 我会背PI小数点后30位  

using std::sqrt;

#include <iomanip>

 

class Application

{

      typedef vector<pair<double,double> > vpdd;

      typedef vector<pair<double,double> >::iterator vpddi;

      int N;

      double R;

      vpdd point;

      public:

      Application()

      {

                    cin>>N>>R;

                    point.resize(N);

                    for (vpddi it=point.begin();

                         it!=point.end();

                         it++)

                        cin>>it->first>>it->second;

      }

      int run()

      {

          double answer=M_PI*R*2.0f;

          for (vpddi it=point.begin();;)

          {

               vpddi to=it++;

               if (it==point.end()) it=point.begin();

               answer+=sqrt((to->first-it->first)

                             *(to->first-it->first)

                            +(to->second-it->second)

                             *(to->second-it->second));

               if (it==point.begin()) break;

          }

          cout<<std::setiosflags(std::ios::fixed)

              <<std::setprecision(2)

              <<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

被这道题整惨了，好无语。用类似矩形切割的方法做。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-16

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#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 Application

{

      int N;

      vector<int> a;

      vector<int> b;

      vector<char> c;

      public:

      Application()

      {

                    cin>>N;

                    a.resize(N);

                    b.resize(N);

                    c.resize(N);

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

                        cin>>a[i]>>b[i]>>c[i];

      }

      int run()

      {

          vector<pair<int,int> > q;    

          q.push_back(make_pair(0,1000000000));

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

          {

              switch (c[i])

              {

                     case ‘w’:

                          q.push_back(make_pair(a[i],b[i]));

                          break;

                     case ‘b’:

                          int end=q.size();

                          for (int j=0;j<end;j++)

                          {

                              if (q[j].first<b[i]&&q[j].second>a[i])

                              {

                                 if (q[j].first<a[i])

                                    q.push_back(make_pair(q[j].first,a[i]));

                                 if (b[i]<q[j].second)

                                    q.push_back(make_pair(b[i],q[j].second));

                              }

                              else q.push_back(make_pair(q[j].first,q[j].second));

                          }

                          q.erase(q.begin(),q.begin()+end);

                          break;

              }

          }

         

          sort(q.begin(),q.end());

         

          pair<int,int> answer=make_pair(0,0);

          for (int i=0,j;i<q.size();i=j)

          {

              int first=q[i].first,second=q[i].second;

              for (j=i+1;j<q.size();j++)

                  if (q[j].first<=second)

                  {

                     if (q[j].second>second)

                        second=q[j].second;

                  }

                  else break;

              if (second-first>answer.second-answer.first)

                 answer=make_pair(first,second);

          }

          cout<<answer.first<<” “<<answer.second<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

 

树形动规，不知为什么，写的第一个程序始终WA#8，后重写，AC，无语。

恩，方程见注释。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-16

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#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 Application

{

      static const int NOTLINKED=~(1<<31);

      int N,Q;

      vector<vector<int> > length;

      public:

      Application()

      {

                    cin>>N>>Q;

                    length=vector<vector<int> >(N,vector<int>(N,NOTLINKED));

                    int a,b,c;

                    for (int i=0;i<N-1;i++)

                    {

                        cin>>a>>b>>c;

                        length[a-1][b-1]=length[b-1][a-1]=c;

                    }

                    if (Q>N-1) Q=N-1;

      }

      /*

      f for father

      l for left child

      r for right child

      f.f[n]=max{

           l.f[i-1]+lenght[f][l]+r.f[n-i-1]+length[f][r],//if have two children

           l.f[n-1]+lenght[f][l],//if have left child

           r.f[n-1]+lenght[f][r],//if have right child

           0//if no child

           }

      */

      vector<vector<int> > get;

      int dp(int f,int have,int ff)

      {

          if (get[f][have]==NOTLINKED)

          {

             int l=NOTLINKED,r=NOTLINKED;

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

                 if ((i!=ff)&&(length[f][i]!=NOTLINKED))

                 {

                    if (l==NOTLINKED)

                    {

                       l=i;

                       continue;

                    }

                    if (r==NOTLINKED)

                    {

                       r=i;

                       continue;

                    }

                 }

             get[f][have]=0;

             int dpl,dpr;

             if (l!=NOTLINKED&&r!=NOTLINKED)

             {

                for (int i=1;i<have;i++)

                {

                    dpl=dp(l,i-1,f)+length[f][l];

                    dpr=dp(r,have-i-1,f)+length[f][r];

                    if (dpl+dpr>get[f][have])

                       get[f][have]=dpl+dpr;

                }

             }

             if (l!=NOTLINKED)

                if (have>0)

                {

                   dpl=length[f][l]+dp(l,have-1,f);

                   if (dpl>get[f][have])

                      get[f][have]=dpl;

                }

             if (r!=NOTLINKED)

                if (have>0)

                {

                   dpr=length[f][r]+dp(r,have-1,f);

                   if (dpr>get[f][have])

                      get[f][have]=dpr;

                }

          }

          return get[f][have];

      }

      int run()

      {

          get=vector<vector<int> >(N,vector<int>(Q+1,NOTLINKED));

          cout<<dp(1–1,Q,NOTLINKED)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

把N分堆，每堆不同，一共有多少分法？
f[n][i]=N分堆后最大的为i一共有几种分法
f[n][n]=1
f[n][i]=sum{f[n-i][j],1<=j<i<n}
answer=sum{f[n][i],1<=i<=n}-1
(减一是减去只有一堆的情况)
CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-16

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#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 Application

{

      int N;

      public:

      Application()

      {

                    cin>>N;

      }

      int run()

      {

          //把N分堆，每堆不同，一共有多少分法？

          //f[n][i]=N分堆后最大的为i一共有几种分法

          //f[n][n]=1

          //f[n][i]=sum{f[n-i][j],1<=j<i<n}

          //answer=sum{f[n][i],1<=i<=n}-1

         

          vector<vector<long long int> > f(N+1,vector<long long int>(N+1,0));

          for (int i=1;i<=N;i++) f[i][i]=1;

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

              for (int i=1;i<n;i++)

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

                      f[n][i]+=f[n-i][j];

          long long int answer=-1;

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

              answer+=f[N][i];

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

变态的最短路，害我写了很多行。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-16

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#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;

 

struct Cube

{

       int left,right,top,forward,bottom,backward;

       inline

       void swap(int& a,int& b,int& c,int& d)

       {

            int s=a;

            a=b;

            b=c;

            c=d;

            d=s;

       }

       inline

       void goup()

       {

            swap(bottom,backward,top,forward);

       }

       inline

       void godown()

       {

            swap(bottom,forward,top,backward);

       }

       inline

       void goright()

       {

            swap(bottom,right,top,left);

       }

       inline

       void goleft()

       {

            swap(bottom,left,top,right);

       }

};

struct Compare

{

       bool operator()(const pair<pair<Cube,pair<int,int> >,int>& a,

                       const pair<pair<Cube,pair<int,int> >,int>& b)

       {

            return a.second>b.second;

       }

};

 

class Application

{

      static const int SIDE=6;

      static const int top=0,

                       bottom=SIDE-1-top,

                       left=1,

                       right=SIDE-1-left,

                       forward=2,

                       backward=SIDE-1-forward;

      static const int SIZE=8;

      static const int ID=24;

      static const int oo=1<<29;

      pair<int,int> f,t;

      vector<int> get_point;

      vector<vector<int> > get_id;

      public:

      Application()

                   :get_point(SIDE),get_id(SIDE,vector<int>(SIDE))

      {

                    char x,y;

                    cin>>x>>y;

                    f.first=x-‘a’;

                    f.second=y-‘1’;

                    cin>>x>>y;

                    t.first=x-‘a’;

                    t.second=y-‘1’;

                    //forward, backward, top, right, bottom and left

                    cin>>get_point[forward]

                       >>get_point[backward]

                       >>get_point[top]

                       >>get_point[right]

                       >>get_point[bottom]

                       >>get_point[left];

      }

      int run()

      {

          //init get_id

          for (int i=0,id=0;i<SIDE;i++)

              for (int j=0;j<SIDE;j++)

                  if ((j!=i)&&(j+i+1!=SIDE))

                     get_id[i][j]=id++;

         

          //dijkstra

          typedef pair<pair<int,int>,int> pre_type;

          vector<vector<vector<int> > >

          dist(SIZE,vector<vector<int> >(SIZE,vector<int>(ID,oo)));

          vector<vector<vector<pre_type> > >

          pre(SIZE,vector<vector<pre_type> >(SIZE,vector<pre_type>(ID)));

         

          std::priority_queue<pair<pair<Cube,pair<int,int> >,int>,

                              vector<pair<pair<Cube,pair<int,int> >,int> >,

                              Compare> q;

          //push start state

          Cube start;

          start.top=top;

          start.bottom=bottom;

          start.left=left;

          start.right=right;

          start.forward=forward;

          start.backward=backward;

          q.push(make_pair(make_pair(start,f),get_point[start.bottom]));

         

          while (!q.empty())

          {

                pair<pair<Cube,pair<int,int> >,int> now=q.top();

                #define getdist(who) (dist[who.first.second.first]\

                                          [who.first.second.second]\

                                          [get_id[who.first.first.top]\

                                                 [who.first.first.left]]\

                                     )

               

                if (getdist(now)==oo)

                {

                   getdist(now)=now.second;

                   #define assignpre(dir,dx,dy)\

                   from.first.first=now.first.first;\

                   from.first.first.go##dir();\

                   from.first.second=make_pair(now.first.second.first+(dx),\

                                               now.first.second.second+(dy));\

                   if ((from.first.second.first>=0)\

                       &&(from.first.second.first<SIZE)\

                       &&(from.first.second.second>=0)\

                       &&(from.first.second.second<SIZE)\

                       &&(getdist(from)+get_point[now.first.first.bottom]==now.second))\

                   {\

                       pre[now.first.second.first]\

                          [now.first.second.second]\

                          [get_id[now.first.first.top]\

                                 [now.first.first.left]]\

                       =make_pair(from.first.second,\

                                  get_id[from.first.first.top]\

                                        [from.first.first.left]\

                                 );\

                   }

                   pair<pair<Cube,pair<int,int> >,int> from;

                   assignpre(left,-1,0);

                   assignpre(right,1,0);

                   assignpre(up,0,1);

                   assignpre(down,0,-1);                  

                   #undef assignpre

                  

                   #define letusgo(dir,dx,dy)\

                   go.first.first=now.first.first;\

                   go.first.first.go##dir();\

                   go.first.second=make_pair(now.first.second.first+(dx),\

                                             now.first.second.second+(dy));\

                   if ((go.first.second.first>=0)\

                       &&(go.first.second.first<SIZE)\

                       &&(go.first.second.second>=0)\

                       &&(go.first.second.second<SIZE)\

                       &&(getdist(go)==oo))\

                   {\

                      go.second=now.second+get_point[go.first.first.bottom];\

                      q.push(go);\

                   }

                   pair<pair<Cube,pair<int,int> >,int> go;

                   letusgo(left,-1,0);

                   letusgo(right,1,0);

                   letusgo(up,0,1);

                   letusgo(down,0,-1);

                   #undef letusgo

                }

                if (now.first.second==t) break;

                q.pop();

                #undef getdist

          }

          stack<pre_type> s;

          s.push(make_pair(q.top().first.second,

                           get_id[q.top().first.first.top]

                                 [q.top().first.first.left]));

          for (pre_type from=make_pair(f,get_id[start.top][start.left]);

               s.top()!=from;)

          {

              pre_type getpre=pre[s.top().first.first]

                        [s.top().first.second]

                        [s.top().second];

              s.push(getpre);

          }

          cout<<q.top().second<<” “;

          while (!s.empty())

          {

                cout<<char(s.top().first.first+’a’)

                    <<char(s.top().first.second+’1′);

                s.pop();

                if (s.empty()) cout<<endl;

                else cout<<” “;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，先把1转到顶部，在使左边尽量小，然后，这个骰子就固定了。然后再编码一下。因为顶都为1，所以就不管了，然后就剩下几个6进制编码。如果两个骰子经过这样的处理后，编码相同，则他们相同。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-15

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#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;

 

struct Dice

{

       static const int SIDE=6;

       static const int TURN=4;

       int left,//the number of points on the left side of the die,

           right,//then on the right side,

           top,//on the top,

           forward,//on the forward side,

           bottom,//on the bottom

           backward;//and on the backward side

       int id;

       void read()

       {

            cin>>left>>right>>top>>forward>>bottom>>backward;

       }

       inline

       void swap(int& a,int& b,int& c,int& d)

       {

            int s=a;

            a=b;

            b=c;

            c=d;

            d=s;

       }

       inline

       void turnLR()

       {

            swap(top,backward,bottom,forward);

       }

       inline

       void turnTB()

       {

            swap(right,forward,left,backward);

       }

       inline

       void turnFB()

       {

            swap(right,top,left,bottom);

       }

       void getid()

       {

            //let top=1

            for (int i=0;(top!=1)&&(i<TURN);i++)

                turnTB();

            for (int i=0;(top!=1)&&(i<TURN);i++)

                turnLR();

            for (int i=0;(top!=1)&&(i<TURN);i++)

                turnFB();

            //assert(top==1);

           

            //let left min

            int min_left=SIDE;

            for (int i=0;i<TURN;i++)

            {

                turnTB();

                if (min_left>left) min_left=left;

            }

            for (int i=0;(left!=min_left)&&(i<TURN);i++)

                turnTB();

           

            id=((((left)*SIDE+right)*SIDE+forward)*SIDE+bottom)*SIDE+backward;

       }

};

 

class Application

{

      int N;

      vector<Dice> dice;

      public:

      Application()

      {

                    cin>>N;

                    dice.resize(N);

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

                        dice[i].read();

      }

      int run()

      {

          map<int,vector<int> > idToIndex;

          map<int,vector<int> >::iterator it;

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

          {

              dice[i].getid();

              idToIndex[dice[i].id].push_back(i+1);

          }

         

          cout<<idToIndex.size()<<endl;

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

              if ((it=idToIndex.find(dice[i].id))!=idToIndex.end())

              {

                 for (int j=0;j<it->second.size();j++)

                     cout<<it->second[j]<<char((j+1==it->second.size())?’\n’:’ ‘);

                 idToIndex.erase(it);

              }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

水题，就是要注意一下细节。特殊对待N=0和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 <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 Application

{

      static const int BASE=10;

      int N;

      vector<int> counter;

      public:

      Application()

                   :counter(BASE,0)

      {

                    cin>>N;

      }

      int run()

      {

          if (N==0) cout<<10<<endl;

          else if (N==1) cout<<1<<endl;

          else

          {

              for (int i=BASE-1;i>1;i–)

                  while (N%i==0)

                  {

                        N/=i;

                        counter[i]++;

                  }

              if (N!=1) cout<<-1<<endl;

              else

              {

                  for (int i=0;i<BASE;i++)

                      for (int j=0;j<counter[i];j++)

                          cout<<i;

                  cout<<endl;

              }

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

URAL1009和URAL1012的加强版，需要高精再加优化。

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()-1–1;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();

}

题目同URAL1009，但是数据范围变了，需要用高精度。

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()-1–1;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()

      {

          BigNumber answer(0);

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

          {

              BigNumber get(1);

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

                  get*=j;

              for (int j=1;j<=N-i*2;j++)

                  get/=j;

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

                  get/=j;

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

                  get*=K-1;

              answer=answer+get;

          }

          answer.print();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}