拆分Nim游戏

给定n堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数n。

第二行包含n个整数，其中第i个整数表示第i堆石子的数量ai。

输出格式

如果先手方必胜，则输出“Yes”。

否则，输出“No”。

数据范围

1≤n,ai≤100

输入样例

2

2 3

输出样例

Yes

题目分析

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：

SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})

特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：

mex(S) = min{x}, x属于自然数，且x不属于S

对于该题可能存在多种上述的不同的有向图，即多个SG函数的值。

由于在该题中我们每一堆石子均可操作，且有集合S内元素的情况。因此我们可以得到每一堆地SG值而后对每一堆地SG值进行异或计算。结果为0则先手必败，否则为先手必胜。

使用异或的结果来判断的原因参考经典Nim游戏的结论·。

对于拆封Nim游戏

首先由题目可知对于每次操作我们可以拿去一堆石子，并拿回另外两堆石子，且石子小于被拿走的堆。

因此可以使用sg函数对每一堆进行计算，（注：此处对于每一堆的拆分时，我们需要计算后续的每种拆分的

可能，同时由于计算中可能出现需要计算大量重复的堆数的sg值，因此此处可以使用记忆化搜索记录已经计算

过的特定堆数的sg值，以优化计算时间。）

此处拆分某一堆可能存在如下图情况。

设某一堆的数量为5

则可以得到情况1

当然也存在另一种的划分情况

如下图

除上述情况还有其他情况存在，需要计算其他情况

因此这样的情况，同时对于5有其他的拆分请况，我们需要计算出所有的请情况的sg值，取除了

集合中sg值外的最小值则为答案

代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N=110;
int n,sg[N],ans;
int getsg(int t)
{
    if(sg[t]!=-1)return sg[t];
    unordered_set<int> map;
    for(int i=0;i<t;i++)
    for(int j=i;j>=0;j--)
        map.insert(getsg(i)^getsg(j));
    for(int i=0;;i++)if(!map.count(i))return sg[t]=i;
}
int main()
{
    cin>>n;
    memset(sg,-1,sizeof(sg));
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        ans^=getsg(a);
    }
    ans?cout<<"Yes":cout<<"No";
    return 0; 
}