先手必胜状态：可以走到某一个必败状态（我走完之后，对手是必败状态）
先手必败状态：走不到任何一个必败状态（我走完之后，对手是必胜状态）

 

x的最高位1假设是k位，那么 一定有一个 ai 的k位为1，那么ai ^ x 之后第k位一定为0。那么一定有 ai ^ x < ai 所以可以拿走 ai-（ ai ^ x）个，那么这堆就剩下 ai-[ ai-（ ai ^ x）] ，即 ai ^ x 个。

异或结果 x = 0 时，我先手拿，留给别人的状态一定不是0，那么我必输。

异或结果 x = 1 时，我先手拿，留给别人的状态一定是0 ，那么我必赢。

就好像，拿石子，两堆石子数不一样，此时异或结果为1，我拿了让他们一样，抛给对方的异或结果就是0，那么我必赢。

891. Nim游戏 - AcWing题库

---

#include<iostream>
using namespace std;int main()
{int n;cin>>n;int res=0;while(n--){int x;cin>>x;res^=x;}if(res) cout<<"Yes"<<endl;else cout<<"No"<<endl;
}

SG函数 到不了的点的最小自然数值

SG(x)=0 必败     SG(x)!=0 必胜

任何一个非0的状态都可以到0  任何一个0的状态都不能到0.

我们先走 可以保证对手永远是0 我们永远是非0 终点状态是0 对手必败.

893. 集合-Nim游戏 - AcWing题库 

---

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
using namespace std;const int N = 110 , M = 10010;
int n,m;
int f[M],s[N];int sg(int x)
{if(f[x]!=-1) return f[x];unordered_set<int> S;for(int i=0;i<m;i++){int sum=s[i];if(x>=sum) S.insert(sg(x-sum));}for(int i=0;;i++)if(!S.count(i))return f[x]=i;
}int main()
{cin >> m;for(int i=0;i<m;i++) cin>>s[i];cin>>n;memset(f,-1,sizeof f);int res=0;for(int i=0;i<n;i++){int x;cin>>x;res^=sg(x);}if(res) puts("Yes");else puts("No");return 0;
}