本题是一道数学题目。初看这道题好象无从下手，但是如果我们考虑另一道题，那么我发现其实这道题很简单。
取豆子问题：从N个盘子里取豆子每个盘子里豆子数都给你，你和MM轮流取，每次只能从一个盘子里取，谁先取光谁赢，MM先取，对于给定的初始状态谁会胜利？
这个问题其实和本题是等价的，假如对于偶数个板，我们把第1号CHESS到第2号CHESS之间的距离看成取豆子问题的豆子，那么假如MM遇到了取豆子问题的必输状态，她在本题上也是必输的，假如MM移动奇数号CHESS向前5格，我就移动它后面的CHESS五格，这样她在取豆子问题上的状态是不变的，假如她移动偶数号板，那么就等同于取豆子问题里MM取了一次豆子，那么由于MM在取豆子问题里是必输的。所以我可以也相应的取一些豆子使MM继续陷入比输态。
下面的问题就是，如何找到取豆子问题的必输状态。
首先我们先分析取豆子问题的比输状态的性质，所谓的比输状态，就是在它不能通过任意的区法到达另一个必输态，而且任何的一个非比输态都可以通过一个取法到达某个必输态。
这个问题也不太好解决。
下面考虑这个问题。
假如在一个N维空间里，有一些星球，如果一个星球的坐标是（A1，A2，。。。AN）
那么对于某个点的坐标为（A1*，A2，A3，。。。AN）（A1*<A1）类似的点，即这个点只有一个坐标轴的值和星球坐标不同，而且这个坐标轴的值还大于星球的相应坐标轴的值。
对于这类点，我们说这个点在这个星球的“引力”上，比如（1，2，3）如果有星球的话，那么（1，2，4），（2，2，3），（5，2，3）都在这个星球的引力上。
问题是，寻找一个布星方案，使得所有的星球都不在其他星球的“引力”上，而且所有的非星球空间都能在某个星球的引力上。

这个问题其实和上面的取豆子问题是等价的，取豆子问题的必输态就是星球问题的星球的位置。
所以显然，星球问题里的布星方案是唯一的。
我们考虑三维空间，那么显然（0，0，0）显然要布上星，而且（011）（110）（101）也必须要布上（否则这些点不可能被星球的引力所覆盖），这个时候我发现，离原点最近的这8个点（2*2*2）的方格的“行为”类似于一颗“大星球”，我称之为“星云”，
事实上，如果我们把所有的星球的位置都改成星云的话，对于一个布星方案如果这样改变只后，还是一个布星方案（但是8*8*8的布星方案就变成了16*16*16的了）
于是，对于一个坐标，我们只要先对它对2的13次方的商求和，如果是偶数，那么把所有的坐标都变成它对2的13次方的余数，然后在对2的12次方求和。。。。。。
如果是奇数，那么就跳出，因为这个点肯定不会有星球存在，MM肯定赢了。。
 
实际上，我们只要把所有的豆子数按位异或然后看最后是不是0就可以了。。。
数据结构：

• 奇数还是没讲啊,奇数的话话好象有点困难,找不到对应的必败状态了 (0) cx19860824 2007-03-17 14:50:28
  • Re:奇数还是没讲啊,奇数的话话好象有点困难,找不到对应的必败状态了 (20) antoniowyn 2008-06-15 16:22:45