$SG$ 函数
$SG$ 函数是用于处理公平组合游戏（$ICG$）。
$ICG$ 性质：
两名玩家。
轮流操作，在任意的有限集合进行操作，并改变局面。（也就是说棋子是“公共”的，不分“黑白”。）
一个局面的合法操作，只取决于游戏局面本身且固定存在，与玩家顺序和任何其它因素都无关。
无法操作的人输掉游戏。
$x,y$ 表示某种状态，$x\to y$ 表示 $x$ 操作一次就能到达 $y$ 的状态。$mex$ 表示一个集合中最小的自然数。例如：$mex(\{1,2,3\})=0$，$mex(\{0,1,3\})=2$。
如果 $sg(x)=n$，说明从当前状态可以转移到 $sg$ 为 $0,1,2,…,n-1$ 的状态。
$sg(x)=0$ 的状态是必败态。此时没有操作可以做，那么就算是输掉比赛。
$Nim$ 游戏
如果只有一堆石头很容易得出：$sg(x)$ 表示剩余 $x$ 颗石子的状态的 $sg$ 的值。
只有一堆，每次可以拿任意个石头。显然，如果还剩 $x$ 颗石头，那么可以转换到还剩 $0,1,2,3,4,5,…,x-1$（每次至少拿一个）的状态。也就是说 $sg(x)=x$。
现在假设有两堆石头，继续玩 $Nim$ 游戏，假设 $sg(n,m)$ 表示剩余石子数分别为 $n$ 和 $m$ 的状态的 $sg$ 值。同样，不难发现，有：
其中：
同样：
但是，如果是 $3,4,5,6,…$ 堆的时候会非常的麻烦。
$SG$ 定理
设 $x,y$ 为 $ICG$ 状态（或者将 $x,y$ 可以看成子游戏），则：$sg(x+y)=sg(x)\oplus sg(u)$
$\oplus$ 就是异或。
如果有 $sg(x)\oplus sg(y)\not =0$ 那么，就一定可以转换到异或和为 $0$，将值较大的转换为和较小的值相同。同样如果 $sg(x)\oplus sg(u)=0$，那么就要想办法转移成不为 $0$ 的状态，如果转移不了了，就形成了必胜状态和必败状态。
- $SG$ 定理推广
设 $x_1,x_2,x_3,…,x_n$ 为 $ICG$ 的状态，则：$sg(x_1+x_2+x_3+…+x_n)=sg(x_1)\oplus sg(x_2)\oplus …\oplus sg(x_n)$
这时就能处理有很多堆石头的 $Nim$ 游戏了，如果有 $n$ 堆石头（可以把每堆石头看成上面说的 $x_1,x_2,…,x_n$ 代表第 $1,2,…,n$ 堆）的异或和为 $0$ 时，游戏必败。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<queue>
using namespace std;
int r_r(){//快读
int k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
int t=r_r();//多测
int main(){
while(t--){
int n=r_r();//每组有多少堆
int s=0;
for(int i=1;i<=n;i++)s^=r_r();//异或每堆的石子数量
//输出
if(!s)puts("No");
else puts("Yes");
}
}SDOI2009 E&D
这道题就需要先处理子游戏最后再得出结果。
将每一组 $S_i$ 看成一个子游戏，
结论：
$sg(x,y)=sg(y,x)$
当 $x,y$ 都是奇数时，$sg(x,y)=0$。
当 $x$ 是偶数时（注意 $x,y$ 的位置可以互换）$sg(x,y)=sg(\frac{x}{2},\lfloor{\frac{y-1}{2}}\rfloor+1)+1$。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
using namespace std;
long long r_r(){//快递
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e3+10;
int main(){
int t=r_r();
while(t--){
int a_s=0;
int n=r_r();
for(int i=1;i<=n/2;i++){
int a=r_r(),b=r_r();
int s_i=0;
while(a||b){//如果是 sg(0,0)，直接返回
if(a&1&&b&1)break;//都是奇数，直接退出
if(a&1)swap(a,b);//保证 a 是偶数
a>>=1;
b=(b-1)>>1;
b++;
s_i++;//累计答案
}
a_s^=s_i;//累计
}
puts(a_s?"YES":"NO");//判断
}
return 0;
}也可写成：
设 $x_i=(x-1)|(y-1)$，
那么 $sg(x_i)=sg(\frac{x_i}{2})+1$
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
using namespace std;
long long r_r(){
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e3+10;
int main(){
int t=r_r();
while(t--){
int a_s=0;
int n=r_r()>>1;
while(n--){
int x_p=0;
int x=(r_r()-1)|(r_r()-1);//计算 x_i
while(x&1){//统计贡献
++x_p;
x>>=1;
}
a_s^=x_p;//累计子任务的贡献
}
puts(a_s?"YES":"NO");//输出结果
}
return 0;
}对于可以用 $SG$ 函数的题而言，关键在于找到 $SG$ 函数。如果实在推不出来，就用暴力枚举，打表找规律。
