POJ 2975 - Nim (Game Theory)
http://www.cnblogs.com/zhj5chengfeng/p/3249083.html
组合数学——Nim取子游戏 太有趣了
http://en.algoritmy.net/article/42137/Nim
http://tristan-xi.org/?p=321
先来看一个更常见的取物品的题目：一堆n个物品，甲乙两人轮流取，每次取1至m个，最后取完者胜。
分析：
1.1-m个物品时，甲稳赢（当然要保证俩人都足够聪明，也就是说甲没傻到当有2个物品时，他却只取一个）
2.m+1个物品时，乙稳赢。此时无论甲取多少个(1-m)，剩下的、乙总能够一次性取完
3.m+2个时，甲稳赢。此时甲拿一个，而无论乙拿几个都会输。其实这时候当乙开始拿物品时，它相当于遇到了第二步中甲所面临的情况（也就是当前物品只剩m+1个，无论自己怎么取，对方都会赢）
4.m+3――2m+1个时，甲稳赢。此时甲只要取2――m个，就会让乙面临m+1这种必输的情况
5.2m+2个时，乙稳赢。此时无论甲取多少个（假设为x），2m+2-x都会落在m+2到2m+1这个区间，此时的乙就面临第四步的情况，所以乙稳操胜券。
6.数学归纳法。我们假设k(m+1)个时，乙稳赢，k(m+1)+1――k(m+1)+m时，甲稳赢，则(k+1)(m+1)时，甲取y个，此时乙面临的个数是(k+1)(m+1)-y==k*(m+1)+m+1-y，介于k(m+1)+1――k(m+1)+m之间，根据假设，也就是说此时乙稳赢。同理，可得当个数在(k+1)(m+1)+1――(k+1)(m+1)+m时，甲稳赢。
前序小结
那么肿么才能让甲稳赢呢？如果n%(m+1)==0，那甲你就别想了，你赢不了了；其他情况，恭喜你，甲赢了，甲的策略就是每次取完都给乙剩下k(m+1)个。上面没提n==0的情况，这个很显然也符合，忘掉了。。。
问题
俩聪明鬼A、B在数盒子里的星星，俩人每人一次只能拿23-28个星星，当某一次某人想拿的时候不够这个数了，就算输。
分析
此题目和上面的很类似，只不过区间变了。
1.0-22个时，A肯定输，因为去不了23――28这么多
2.23-27时，A稳赢，因为可以随便一手抓掉。
3.28-50时，A稳赢，此时A只要取28个，B就面临A在第一步时的处境了
4.51-73时，B稳赢，因为不管A抓多少个（当然，必须是在23――28之间），此时剩下的数肯定在23――50之间，也就是说B面临了A在二、三步的情况，所以B稳赢
5.74-101时，A稳赢，分两种情况：74-96时，A先抓23个，此时剩下51-73，B面临A在第四步的情形，所以A稳赢；97-101时，甲取28个，这样剩69――73个，仍是A赢
6.。。。和前序一样数学归纳法，可以证得51*k――51*k+22时，B稳赢，其它情况A稳赢。
总结规律：
根据上面两个例子，我们可以大胆假设，甲、乙取物品，每次只能取a――b之间的数量，一共sum个物品，则甲稳输的情况位于(a+b)*k到(a+b)*k+(a-1）之间
证明
第一步：当a==b时，显然，最简单了，只要求ans = sum/a，看a是否为偶数，偶数就会输，也就是sum/a%2为0时，甲就会输。公式也就变成了2a*k――2a*k+a-1之间，除以a，商为2*k，2*k%2==0，所以满足公式。
第二步:a==1,b==m时，这也就是前言中的情况，带入公式得到(1+m)*k――(1+m)*k+0，也就是前言中推导出来的(1+m)*k时，乙稳赢，所以满足公式。
第三步：假设i――j的时候满足，也就是说当物品个数位于(i+j)*k到(i+j)*k+(i-1)时，乙稳赢，其他情况，甲稳赢。
则当a==i,b==j+1时：
1.0――i-1时，乙稳赢。
2.i――j时，甲稳赢
3.j+1――i+j时，此时甲取j+1个，此时剩下0到i-1个物品，此时乙面临甲在第一步时的败局，所以甲稳赢。
4.同理，数学归纳法，可证。
当a==i+1，b==j时，同理，也可证。
总结论
甲、乙取物品，每次只能取a――b之间的数量，则甲稳输的情况时总物品的数量在(a+b)*k到(a+b)*k+(a-1）之间，其它数量的时候甲稳赢，所以，甲每次需要做的就是取适量的物品，使得乙面对的物品在(a+b)*k到(a+b)*k+(a-1）之间。
http://blog.csdn.net/doc_sgl/article/details/8898255
http://www.cnblogs.com/zhj5chengfeng/p/3249083.html
有 n(1≤n≤1000) 堆石子，每堆石子数量为 1 到 1,000,000,000 之间的一个整数。两人玩游戏。每回合，游戏者必须从某堆中取走至少一个石子，取走最后一个石子的人获胜。问先手第一步有多少种走法使得他/她获胜
做法分析
Nim 游戏的简单变形
说明：下面的 '^' 符号表示 “异或” 的意思
先求出所有的石子数量的 Nim 和，设为 sum。
对于某一堆石子，设石子数量为 Ai，sum^Ai 就得到了除去该堆石子，其余石子数量的异或和。假设先手第一步在这一堆中取石子，如果取走石子后，这一堆剩余石子 Bi 个，要保证先手必胜，必然下一个局面是后手必胜，于是有：sum^Ai^Bi=0，也就是说：
sum^Ai=Bi
看到上面的式子，不难得出结论：在 Ai 中取走 Ai-(sum^Ai) 个石子是第一步在 Ai 中取石子的唯一获胜方式，当然前提是：
Ai≥sum^Ai
于是利用上面的结论对每一堆石子判断一下即可
int main() 10 { 11 while(scanf("%d", &n), n!=0) 12 { 13 int ans=0, sum=0; 14 for(int i=0; i<n; i++) scanf("%d", &A[i]), ans^=A[i]; 15 for(int i=0; i<n; i++) if((ans^A[i])<=A[i]) sum++; 16 if(ans==0) sum=0; 17 printf("%d\n", sum); 18 } 19 return 0; 20 }
hdu 1850 Being a Good Boy in Spring Festival
Nim游戏（又名取石子问题）—博弈论入门（一）int main()
{
int n,sum,s;
int dig[102];
while(cin>>n&&n)
{
sum=0;
for(int i=0;i<n;i++)
{
scanf("%d",&dig[i]);
sum^=dig[i];
}
if(sum==0)
printf("0\n");
else
{
int cnt=0;
for(int i=0;i<n;i++)
{
s=sum^dig[i];
if(dig[i]>=s)
cnt++;
}
printf("%d\n",cnt);
}
}
return 0;
}
10165 - Stone Game组合数学——Nim取子游戏 太有趣了
为了进一步理解Nim取子游戏，我们考查某些特殊情况。如果游戏开始时只有一堆硬币，游戏人I则通过取走所有的硬币而获胜。现在设有2堆硬币，且硬币数量分别为N1和N2。游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。设N1！=N2，游戏人I从大堆中取走的硬币使得两堆硬币数量相等，于是，游戏人I以后每次取子的数量与游戏人II相等而最终获胜。但是如果N1= N2，则：游戏人II只要按着游戏人I取子的数量在另一堆中取相等数量的硬币，最终获胜者将会是游戏人II。这样，两堆的取子获胜策略就已经找到了。
如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：
as + bs + … + ms 是偶数
……
a1 + b1 + … + m1 是偶数
a0 + b0 + … + m0是偶数
归根结底，Nim取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。
赢得尼姆(Nim)游戏
得到这个取胜秘密的取决于把堆的大小写成二进制形式，接着把这些数字加起来——但是别用一般的加法运算，准确的方法应该叫做Nim加法（Nim addition）。
现在如果你是玩家A，所以你先走。接着假设现在堆里的Nim和不等于0.你的策略将会是这样:如果可能尽可能使得下一个Nim和，也就是你动作后的Nim和为0.这也意味着无论B如何动作通过事实1可知，B的这个动作会把下个Nim和变得不为0.
赢得尼姆(Nim)游戏
得到这个取胜秘密的取决于把堆的大小写成二进制形式，接着把这些数字加起来——但是别用一般的加法运算，准确的方法应该叫做Nim加法（Nim addition）。
现在如果你是玩家A，所以你先走。接着假设现在堆里的Nim和不等于0.你的策略将会是这样:如果可能尽可能使得下一个Nim和，也就是你动作后的Nim和为0.这也意味着无论B如何动作通过事实1可知，B的这个动作会把下个Nim和变得不为0.
- void main()
- {
- int a,b[100],i,c;
- scanf("%d",&a);
- for(i=0;i<a;i++)
- scanf("%d",&b[i]);
- c=0;
- for(i=0;i<a;i++)
- {
- c=c^b[i];
- }
- if(c==0)
- printf("后手赢/n");
- else
- printf("先手赢/n");
- }
Winning strategy
At first, we have to convert a number of objects (matchsticks) to the binary numeral system. Let's suppose that we have 3 heaps with 3, 4 and 5 objects. The player may remove at most 3 objects from exactly one heap.
Now we sum the binary sum sizes together, while neglecting carries from one digit to another (we performXOR operation). The result is called nim-sum.
To get into the winning position, we must always make sure that the nim-sum is equal to zero. In this case, we have to perform such operation, which will set the middle digit to zero – we have to remove two objects from the first heap.
It can be proved, that the opponent cannot turn the game – he cannot make the nim-sum equal to zero and if he takes any step, we will be able to reset nim-sum again.
Misère Nim modificat
(转载)Nim游戏博弈(收集完全版)http://tristan-xi.org/?p=321
先来看一个更常见的取物品的题目：一堆n个物品，甲乙两人轮流取，每次取1至m个，最后取完者胜。
分析：
1.1-m个物品时，甲稳赢（当然要保证俩人都足够聪明，也就是说甲没傻到当有2个物品时，他却只取一个）
2.m+1个物品时，乙稳赢。此时无论甲取多少个(1-m)，剩下的、乙总能够一次性取完
3.m+2个时，甲稳赢。此时甲拿一个，而无论乙拿几个都会输。其实这时候当乙开始拿物品时，它相当于遇到了第二步中甲所面临的情况（也就是当前物品只剩m+1个，无论自己怎么取，对方都会赢）
4.m+3――2m+1个时，甲稳赢。此时甲只要取2――m个，就会让乙面临m+1这种必输的情况
5.2m+2个时，乙稳赢。此时无论甲取多少个（假设为x），2m+2-x都会落在m+2到2m+1这个区间，此时的乙就面临第四步的情况，所以乙稳操胜券。
6.数学归纳法。我们假设k(m+1)个时，乙稳赢，k(m+1)+1――k(m+1)+m时，甲稳赢，则(k+1)(m+1)时，甲取y个，此时乙面临的个数是(k+1)(m+1)-y==k*(m+1)+m+1-y，介于k(m+1)+1――k(m+1)+m之间，根据假设，也就是说此时乙稳赢。同理，可得当个数在(k+1)(m+1)+1――(k+1)(m+1)+m时，甲稳赢。
前序小结
那么肿么才能让甲稳赢呢？如果n%(m+1)==0，那甲你就别想了，你赢不了了；其他情况，恭喜你，甲赢了，甲的策略就是每次取完都给乙剩下k(m+1)个。上面没提n==0的情况，这个很显然也符合，忘掉了。。。
问题
俩聪明鬼A、B在数盒子里的星星，俩人每人一次只能拿23-28个星星，当某一次某人想拿的时候不够这个数了，就算输。
分析
此题目和上面的很类似，只不过区间变了。
1.0-22个时，A肯定输，因为去不了23――28这么多
2.23-27时，A稳赢，因为可以随便一手抓掉。
3.28-50时，A稳赢，此时A只要取28个，B就面临A在第一步时的处境了
4.51-73时，B稳赢，因为不管A抓多少个（当然，必须是在23――28之间），此时剩下的数肯定在23――50之间，也就是说B面临了A在二、三步的情况，所以B稳赢
5.74-101时，A稳赢，分两种情况：74-96时，A先抓23个，此时剩下51-73，B面临A在第四步的情形，所以A稳赢；97-101时，甲取28个，这样剩69――73个，仍是A赢
6.。。。和前序一样数学归纳法，可以证得51*k――51*k+22时，B稳赢，其它情况A稳赢。
总结规律：
根据上面两个例子，我们可以大胆假设，甲、乙取物品，每次只能取a――b之间的数量，一共sum个物品，则甲稳输的情况位于(a+b)*k到(a+b)*k+(a-1）之间
证明
第一步：当a==b时，显然，最简单了，只要求ans = sum/a，看a是否为偶数，偶数就会输，也就是sum/a%2为0时，甲就会输。公式也就变成了2a*k――2a*k+a-1之间，除以a，商为2*k，2*k%2==0，所以满足公式。
第二步:a==1,b==m时，这也就是前言中的情况，带入公式得到(1+m)*k――(1+m)*k+0，也就是前言中推导出来的(1+m)*k时，乙稳赢，所以满足公式。
第三步：假设i――j的时候满足，也就是说当物品个数位于(i+j)*k到(i+j)*k+(i-1)时，乙稳赢，其他情况，甲稳赢。
则当a==i,b==j+1时：
1.0――i-1时，乙稳赢。
2.i――j时，甲稳赢
3.j+1――i+j时，此时甲取j+1个，此时剩下0到i-1个物品，此时乙面临甲在第一步时的败局，所以甲稳赢。
4.同理，数学归纳法，可证。
当a==i+1，b==j时，同理，也可证。
总结论
甲、乙取物品，每次只能取a――b之间的数量，则甲稳输的情况时总物品的数量在(a+b)*k到(a+b)*k+(a-1）之间，其它数量的时候甲稳赢，所以，甲每次需要做的就是取适量的物品，使得乙面对的物品在(a+b)*k到(a+b)*k+(a-1）之间。
http://blog.csdn.net/doc_sgl/article/details/8898255
