Nim游戏拓展
扯淡
来补坑。
谈及一下Nim游戏的应用。
Nim游戏
结论是：
如果石子堆的异或和为0，那么先手必败，反则先手必胜。
小练习
给定n个框，从左到右排列，每个框内初始可能有一些球。两位玩家轮流操作，每次操作可以选择一个框，然后把一个求丢到其左边的一个框内（如果左边没框则不能这么操作）。
求先手必胜/后手必胜的充要条件？
思路：
我们把每个球的位置拿出来，从0开始标号。
发现一次操作就是把这个球的位置减少若干。
那么就转换为了Nim游戏！
Topcoder SRM 565-500
按如下方式定义一个游戏：给定 l , r ( l≤r )，定义可重数集 S={x∈Z|l≤x≤r} 。
定义一次操作为选中数集中的某个数 num 然后把它变成一个不等于他自己的因数。
两个玩家轮流操作，没有合法操作(即 S 中所有数都是 1 )的玩家失败。
题目给定两个数 L 和 R ，问有多少种 L≤l≤r≤R 满足 l 和 r 定义的游戏先手必胜。
1≤L≤R≤10^9，R−L≤10^6
思路：
首先不难想到，把一个数字分解质因数，得到x=pai(pi^ci)。接下来我们发现这个数字可以变换的次数就是pai(ci+1)。这就变为了一个Nim游戏。
那么分解质因数以后，问题转换为在[L,R]内有多少子区间[li。。ri]的xor和为0。
那么转换为前缀异或和，用一些高效的数据结构即可。
关于分解质因数的内容，王队长说我们可以用一种筛法。当然Pollard_rho强行卡应该是可以的，不过据说这个筛法可以做到比较小的时间。原理大概是枚举一个数字的倍数的感觉。
反正本人才疏学浅没有用过。
阶梯博弈
给出n+1阶楼梯，编号为0,1...n。现在每一阶阶梯上有一堆石子。可以选择一个阶梯上的若干石子扔到下一个阶梯。
无法操作者为败。
求先手必胜/后手必胜的条件。
思路：
我们发现，编号为偶数的都是无用的。因为对于必胜方，如果对方从偶数第2k阶扔x个石子到第2k+1阶，那么我们可以选择从奇数第2k+1阶扔x个石子到第2k+2阶。
然后第0阶是终止状态。
也就是说，如果一枚石子从奇数阶被扔到了偶数阶，这枚棋子就相当于被永远扔掉了。
那么这就是奇数阶的石子在玩Nim游戏！
所以我们只需要把所有奇数阶的棋子拿出来，然后做xor和。如果xor和为0，则先手必败，反则先手必胜。
BZOJ 1115
有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。
两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件。
谁没有石子可移时输掉游戏。问先手是否必胜。
思路：
首先我们差分一下。令T[i]=A[i]-A[i-1]。那么一次操作相当于在差分数组上把位置p的x枚石子转移到p+1上。
那么就变为了阶梯博弈。
BestCoder#90 prob.1002
给定一棵有根树，每个节点上可能有一些石子。2位玩家轮流操作，每次操作可以选择一个节点，取上面的一些石子移动到它的父亲上（如果没有父亲则操作不合法）。
问先手是否必胜。
思路：
拿这棵树的深度当做阶梯即可。
（纯属抄PPT……Orz一下王队长吧）