博弈

一些概念
奇异局势(必败点)：当前面对这个状态者必败
非奇异局势(必胜点)：当前面对这个状态者必胜
SG值：一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。
后继点：也就是按照题目要求的走法（比如取石子可以取的数量，方法）能够走一步达到的那个点。
例1.Nim-Game
题意：
有三堆各若干个物品，两个人轮流从某一堆取任意多的
物品，规定每次至少取一个，多者不限，最后取光者得胜。

Input
1 2 3

Output
lose

把当前局势用(a,b,c)来表示
给出三种情况的奇异局势
(0，0，0)
(0，n，n)
(a，b，c)
前两种比较容易想到，第三种一般情况下怎么才是奇异局势呢？
假使我们有一个非奇异局势(x，y，z),假设 x < y < z,我们只要将 z 变为 x ^ y,因为有如下的运算结果: (x ^ y) ^ (x ^ y) = 0。要将z 变为x ^ y，只要从 z中减去 z - (x ^ y).
用^的加密解密思想来想，就是对于偶数次操作来说不会改变当前局势

例2. S-Nim
题意：
有n堆石子，每堆石子个数已知，两人轮流从中取石子，每次可取的石子数x满足x属于集合S(k)={s1,s2,s3...sk-1},并且只能在一堆石子中取，问先拿者是否有必胜策略？
Input
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12

5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12

0

Output
LWW
WWL

分三步：

1.可将问题转化为n个子问题，每个子问题分别为： 从一堆x颗石子中取石子，每次可取的石子数为集合S(k)中的一个数

2.分析(1)中的每个子问题,得:SG(x) = mex(SG[x-s[i]])(1 < i < k)

3.SG函数的应用，根据Sprague-GrundyTherem：g(G)=g(G1)^g(G2)^g(G3)^…^g(Gn) 即游戏的和的SG函数值是它的所有子游戏的SG函数值的异或，即 SG(G) = SG(x1)^SG(x2)^…^SG(xn),故若SG(G)=0那么必输

有了sg函数基本上简单的博弈都没有问题了，但碰到比较难的博弈的时候就会出现问题，比如下面一个题。

例3 Lieges of Legendre
题意：
有n（1<=n<=1e5）个数值a[]，每个数值的范围都在[1,1e9]范围。
Kevin先手，Nicky后手。当一个人再也无法操作的时候认为这个人败。
操作有两种——
1.选择一个数，做-1操作，数如果变成0，就移除。
2.选择一个偶数，设这个偶数为2x，我们把这个数移除，并替换成k个x
input
2 1
3 4
output
Kevin
input
1 2
3
output
Nicky

首先和上面一样，分成三步来解决这个问题。
1.这个问题可以拆分成找每个数的sg函数
2.分析（1）中的每个子问题，sg函数与k的奇偶性相关
3.合并求出全局sg函数

SG值一般的计算方法可以是DP打表，然而这道题的数值范围巨大，没法打表，所以我们肯定要找一下规律，以前找规律就是打出答案，盲目的求解，有了sg函数可以让大问题拆分成小问题来做，我们可以先找sg函数的规律，解决了sg函数，就能解决这个问题

我们来对第二步进行讨论
1.假设k是偶数的情况
如果k为偶数，那么对于操作2，我们会分裂出偶数个f(x)，而这偶数个f(x)的异或和显然是0。
所以，在k为偶数的情况下，我们可以算出
sg[0]=0;
sg[1]=1;
sg[2]=2;
sg[3]=0;
sg[4]=1;
sg[5]=0;
sg[6]=1;
sg[7]=0;
sg[8]=1;
2.假设k是奇数的情况
如果k为奇数，那么对于操作2，我们会分裂出奇数个f(x)，而这奇数个f(x)的异或值相消，就只剩下了一个f(x)
所以，在k为奇数的情况下，我们可以算出
sg[0]=0;
sg[1]=1;
sg[2]=0;
sg[3]=1;
sg[4]=2;
sg[5]=0;
sg[6]=2;
sg[7]=0;
sg[8]=1;
sg[9]=0;
sg[10]=1;
sg[11]=0;
sg[12]=1;
sg[13]=0;
sg[14]=1;
sg[15]=0;
sg[16]=2;
sg[17]=0;
sg[18]=1;
sg[19]=0;
sg[20]=2;
然后我们就总就出了下面的关系，这比起纯粹的胜负判定是好找多了
int odd(int x)
{
if(x==0)return 0;
if(x==1)return 1;
if(x==2)return 0;
if(x>=5&&(x&1))return 0;
int two=0;while(x%2==0){x/=2;++two;}
if(x==3)return two&1?2:1;
else return two&1?1:2;
}

sg[1]要特判为1，sg[2]要特判为0，其他情况，与x>=5且x为奇数的情况相同。