N 枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开始对硬币按1 到N 编号。
第一，游戏者根据某些约束翻硬币，但他所翻动的硬币中，最右边那个硬币的必须是从正面翻到反面。
第二，谁不能翻谁输。
有这样的结论：局面的SG 值为局面中每个正面朝上的棋子单一存在时的SG 值的异或和。即一个有k个硬币朝上，朝上硬币位置分布在的翻硬币游戏中，SG值是等于k个独立的开始时只有一个硬币朝上的翻硬币游戏的SG值异或和。比如THHTTH这个游戏中，2号、3号、6号位是朝上的，它等价于TH、TTH、TTTTTH三个游戏和，即sg[THHTTH]=sg[TH]^sg[TTH]^sg[TTTTTH].我们的重点就可以放在单个硬币朝上时的SG值的求法。
这一题是每次可以翻动一个、二个或三个硬币。
初始编号从0开始。如果先手胜则输出NO
sg[i] 表示 第i个位置上为正 其余位置为反面
只有一枚硬币时 正，先手必胜，则它的后继状态的sg值为0 所以sg[0]=1.
有2枚硬币时 反正 翻2个 后继状态为sg[0] 翻1个 后继状态为 所以sg[1] = 2
....
Sample Input
0
1 //n
0 //正面朝上硬币的位置
4
0 1 2 3
Sample Output
Yes
No
Yes
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# include <queue>
# include <list>
# define LL long long
using namespace std ; int a[]; int SG(int x)
{
int tmp = x;
int cnt = ;
while(tmp)
{
if(tmp&)cnt++;
tmp>>=;
}
if(cnt&)return *x;
else return *x + ;
} int main()
{
int n;
while(scanf("%d",&n)==)
{
for(int i = ;i < n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
n = unique(a,a+n)-a;
int sum = ;
for(int i = ;i < n;i++)
sum ^= SG(a[i]);
if(sum)printf("No\n");
else printf("Yes\n");
}
return ; }
打表 找规律
发现 1 2 4 7 8.... 这些的sg值为本身的两倍 这些数字的二进制只含有奇数个1 剩余的sg值为本身的2倍+1 （比如0 3 5 6 9这些）
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <string>
# include <cmath>
# include <queue>
# include <list>
# define LL long long
using namespace std ; int sg[];
bool vis[]; int mex(int n) //求N的SG值
{
if(sg[n] != -)return sg[n];
memset(vis,false,sizeof(vis));
vis[] = ; //只有1枚硬币，后继必败
int i , j ;
for (i = ; i < n ; i++)
vis[mex(i)] = ;
for (i = ; i < n ; i++)
for (j = ; j < i ; j++)
vis[mex(i)^mex(j)] = ;
for(i = ;;i++)
if(vis[i] == false)
{
sg[n] = i;
break;
}
return sg[n];
} int main()
{ memset(sg,-,sizeof(sg));
sg[] = ;
for(int i = ;i <= ;i++)
sg[i] = mex(i); cout<<sg[]<<" ";
for(int i=;i<=;i++)
{
cout<<sg[i]<<" ";
if(i%==)
cout<<endl;
} return ;
}