序
Nim Game问题是博弈问题中的重头戏，也是现在信息学竞赛中考察最多的。Nim Game往往与xor运算相联系，同时又引出了很多的分支，最经典的是Nim-k、anti-Nim、Staircase Nim、take&break四个拓展问题。此外还有Misère Nim，概率问题。
1.传统的Nim Game
问题描述：
有若干堆石子，两个游戏玩家轮流取，每次可以在一堆中取若干个，至少取一个，可以一次取完，问是否有必胜策略。
问题分析：
对于一个局面，令S = P1 ^ P2 ^ P3 ^ …^ Pn。若S = 0则为先手必败局面，否则为先手必胜局面。
证明：
若当P1 = P2 = …. = Pn = 0 时，S = 0 ，满足终状态是先手必败局面。
若S = 0 ，即P1 ^ P2 ^ P3 ^ …^ Pn = 0，若取堆i中的石子，Pi – > Pi ’，S -> S’ ，Pi > Pi’ ，则Pi ^ Pi’ != 0 。所以S’ ^ Pi^ Pi’ = S = 0 ，即S’ = Pi ^ Pi’ != 0 。满足先手必败局面的所有子局面都是N局面。
若S != 0 ，设S的二进制位是A1…An ，考虑第一位是1的。在P中取出该位同是1的，不妨设为P1 。可知P1 ^ S < P1 ，令P1’ = P1 ^ S 。可知P1’ ^ P2’ ^ … ^ Pn = 0 。即先手必胜局面存在至少一个子局面是先手必败局面。（证完）
Program：
#include
using namespace std ;
int main(){
int s=0 , n, x;
cin >> n;
for (int i=1;i<=n;i++)
cin >> x, s ^= x;
cout << (s!=0 ? "win":"lose") << endl;
}
…
.
2.Nim-k Game
问题描述：
两人轮流对N堆石子进行操作，每堆分别有Pi颗。每人每次可以从最多K堆中取走任意多颗石子，但至少要取走一颗石子。谁取到最后一颗谁胜利。什么情况下先手必胜，什么情况下后手必胜
问题分析：
这个题目是Nim Game的拓展问题。与Nim Game不同点在于这次可以在k堆中取。
首先，我们要来分析一下异或运算，二进制的异或运算我们可以看作是数字的不进位加法mod 2。那么我们同样定义k进制异或运算为数字的不进位加法mod k。那么，从Nim Game推广，Nim-k Game能不能利用 (k+1) 进制异或来解决呢？不难证明，这个方法是成立的。我们可以看一个例子：
K=2
3—————— 1 1
5—————— 1 0 1
10—————— 1 0 1 0
15————— 1 1 1 1
2 2 0 0 (mod 3)
所以这是先手必胜局面，第一步取10->6 15->7可以到达一个先手必败局面。
3—————— 1 1
5—————— 1 0 1
6—————— 0 1 1 0
7—————— 0 1 1 1
0 0 0 0 (mod 3)
这样，我们就可以利用类似Nim Game的方法解决Nim-k Game了。
#include
using namespace std ;
int n , k , x ;
int Ans[32] ;
int main() {
cin >> n >> k ;
for (int i=0;i<32;i++) Ans[i] = 0 ;
for (int i=1;i<=n;i++){
cin >> x ;
for (int j=0;j<32;j++) Ans[j] += ( x >> j ) & 1 ;
}
int i;
for (i=0;i<32;i++) if (Ans[i] % (k+1) != 0) break ;
cout << (i<32 ? "win" : "lose") << endl;
}
...
