条件
- 由两名玩家交替行动;
- 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;
- 不能行动的玩家判负;
int s[N], f[M]; //s[]存储每个局面的初始状态,f[]存储每个状态的sg值
int sg(int x) //求x对应的sg值
{
if (f[x] != -1) //记忆化
{
return f[x];
}
unordered_set<int> S; //存储所有子局面的sg值
for (int i = 0; i < x; i++) //具体问题的子局面递归逻辑
{
for (int j = 0; j <= i; j++)
{
S.insert(sg(i) ^ sg(j));
}
}
for (int i = 0;; i++) //MEX运算
{
if (!S.count(i))
{
return f[x] = i;
}
}
}
int main()
{
std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(f, -1, sizeof f); //初始化
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
int res = 0;
for (int i = 0; i < n; i++) //若所有局面的sg值异或和(res)非零,先手必胜,否则先手必败
{
res ^= sg(s[i]);
}
if (res)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}