POJ2975[Nim]

利用(SG^k[i])^(k[i]-(k[i]-(SG^k[i])))=0,推走哪一步可以让对方处于必败态。


SG为起初所有k[]的NIM和(即异或结果)。


那么SG^k[i]=所有k[]中除去k[i]后的NIM和(由a^b=c等价于a=b^c得)。


所以当k[i]>(k[i]-(SG^k[i]))时,从k[i]中取走(k[i]-(SG^k[i])),剩下(k[i]-(k[i]-(SG^k[i])))=(SG^k[i])。


然后(SG^k[i])^(SG^k[i])=0,是一个必败态。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-6-18


DESCRIPTION:


http://acm.pku.edu.cn/JudgeOnline/problem?id=2975


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <vector>


using std::vector;


 


class Application


{


      int n;


      vector<int> k;


      public:


      Application()


      {


                   std::ios::sync_with_stdio(false);


      }


      int run()


      {


          for (cin>>n;n;cin>>n)


          {


              k.resize(n);


              int SG=0,answer=0;


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


              {


                  cin>>k[i];


                  SG^=k[i];


              }


              if (SG)


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


                     if ((SG^k[i])<k[i]) answer++;


                     //(SG^k[i])^(k[i]-(k[i]-(SG^k[i])))=0


              cout<<answer<<endl;


              k.clear();


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}