复杂的Nim博弈问题

前言

两道稍微复杂一些的Nim博弈问题，用到了非常神奇的异或方式。

HDU-2176 取(m堆)石子问题

题目描述：

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.

Input

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出.

Output

先取者负输出No.先取者胜输出Yes,然后输出先取者第1次取子的所有方法.如果从有a个石子的堆中取若干个后剩下b个后会胜就输出a b.参看Sample Output.

Sample Input

2
45 45
3
3 6 9
5
5 7 8 9 10
0

Sample Output

No
Yes
9 5
Yes
8 1
9 0
10 3

题目分析

这种从m堆里去石子的题目，可以拆分成一个一个的单独的Nim博奕，先说结论，只要满足每一堆的异或为0，就是先手必输，后手必胜，异或不为0，则是先手获胜。
这里给出分析过程：
对于某个局面(a1,a2,…,an)，若a1^ a2 ^ …^ an不为0，一定存在某个合法的移动，将ai改变成ai’后满足a1^ a2^ …^ ai’^ …^ an=0。不妨设a1^ a2^ …^ an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1。因为只有这样，才能使k的最高位为1。而且我们知道ai^ k < ai，所以此时我们ai^ k去替换ai，此时原式就变成了a1^ a2^ … ^ ai^ … ^ an^ k = k ^ k = 0。
这个操作说明了我们可以通过一次操作使任何一个异或不为0的序列变成异或为0的序列，而后手的操作一定会打破这种情况，如此往复会得到全0的结果，也就是先手会获得胜利。
类似的，如果开始情况下异或为0， 则先手会打破这种情况，后手就会获得胜利。
至于题目中要求的操作，我们可以通过什么提到的方式来实现，即求出所有比ai小的ai^ k，也就是替换后的结果。

代码实现

---

HDU-1850 Being a Good Boy in Spring Festival

题目描述：

一年在外 父母时刻牵挂
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧

陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐

如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢～

下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负，我只想问大家：
——“先手的人如果想赢，第一步有几种选择呢？”

Input

输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1<M<=100)，表示扑克牌的堆数，紧接着一行包含M个整数Ni(1<=Ni<=1000000，i=1…M)，分别表示M堆扑克的数量。M为0则表示输入数据的结束。

Output

如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。

Sample Input

3
5 7 9
0

Sample Output

1

题目分析

本质上来讲这一题和上一题没有什么区别，只是把上一题的情况放在了具体的环境中，最后的输出由具体方案变成了方案数量，解题思路和上一题基本一样，每一堆的牌数求异或，若为0则输出0，若不为0则在后面求方案的时候计数，最后输出即可。

代码实现

总结

这两道题目就不算简单了，参考了一些资料才搞懂里面的道理。