证明多个独立局面的SG值，等于这些局面SG值的异或和

$SG$函数和$\text{mex}$函数的定义

SG 函数定义于有向无环图$G=(V, E)$中，对于节点$v\in V$，$SG(v)=\text{mex}\{SG(u)|(v, u)\in E\}$，其中$\text{mex}$（minimum excludant）是对自然数集合的运算，其值为集合中未出现的最小自然数。例如，若集合$S = \{0, 1, 3\}$，则$\text{mex}(S)=2$.

$n$个有向图组成的组合游戏

设有$n$个独立局面$G_1=(V_1, E_1), G_2=(V_2, E_2),\cdots, G_n=(V_n, E_n)$，对应的初始状态为$v_1, v_2,\cdots, v_n$。组合后的游戏$G=(V, E)$，状态可表示为$(v_1, v_2,\cdots, v_n)$.

一次操作是在某一个独立局面$G_i$中进行操作，改变$v_i$的状态到$u_i$（$(v_i, u_i)\in E_i$​），而其他局面状态不变.

证明

对于$n$个独立局面组合的游戏$(v_1, v_2,\cdots, v_n)$，设
$$ k = SG(v_1)\oplus SG(v_2)\oplus\cdots\oplus SG(v_n) $$
我们必须要证明$k$是$n$个独立局面组合的游戏$(v_1, v_2,\cdots, v_n)$的$SG$值，因此根据$SG$值的定义，必须证明后继局面的$SG$值可以取到$0$到$k-1$的任意值，但不能取到$k$.

$k = 0$是必败状态且$k\ne 0$是必胜状态

当$k = 0$时，对于任意的操作，比如在局面$G_i$中进行操作，改变$v_i$到$u_i$，新的$SG$值异或和为
$$ SG(v_1)\oplus\cdots\oplus SG(u_i)\oplus\cdots\oplus SG(v_n)=(SG(v_1)\oplus\cdots\oplus SG(v_n))\oplus(SG(u_i)\oplus SG(v_i)) $$
因为$SG(v_1)\oplus\cdots\oplus SG(v_n)=0$，而$SG(u_i)\neq SG(v_i)$，所以
$$ SG(v_1)\oplus\cdots\oplus SG(u_i)\oplus\cdots\oplus SG(v_n)\neq0 $$
因此无论怎么操作只能变为必胜状态，故$k=0$​是必败状态。

当$k \ne 0$时，设$k$的二进制表示中最高位的$1$在第$m$位。那么至少存在一个$i$，使得$SG(v_i)$的二进制表示第$m$位是$1$。设$u_i$是$v_i$的一个后继状态，使得$SG(u_i)=SG(v_i)\oplus k$（这样的$u_i$一定存在，因为$SG(v_i)\oplus k<SG(v_i)$，根据$SG$函数定义可以找到这样的后继状态）。此时新的$SG$值异或和为
$$ \begin{aligned} SG(v_1)\oplus\cdots\oplus SG(u_i)\oplus\cdots\oplus SG(v_n) =&(SG(v_1)\oplus\cdots\oplus SG(v_n))\oplus(SG(u_i)\oplus SG(v_i)) \\ =&k\oplus(SG(u_i)\oplus SG(v_i)) \\ =&0 \end{aligned} $$
即可以通过一种操作使得到的状态是必败状态，所以$k\ne 0$​是必胜状态。

后继状态的$SG$值不能取到$k$

当在某个独立局面$G_i$中进行一次合法操作，将状态$v_i$改变为$u_i$（$(v_i, u_i)\in E_i$）时，新的$SG$值异或和变为,
$$ SG(v_1)\oplus\cdots\oplus SG(u_i)\oplus\cdots\oplus SG(v_n) $$
由于$SG(u_i)\neq SG(v_i)$（因为是不同的后继状态，根据$SG$函数的定义确定其不同），那么新的异或和$SG(v_1)\oplus\cdots\oplus SG(u_i)\oplus\cdots\oplus SG(v_n)$与原来的$k = SG(v_1)\oplus SG(v_2)\oplus\cdots\oplus SG(v_n)$​必然不同。

后继状态的$SG$值可以取到$0$到$k - 1$

设$k$的二进制表示为$k = b_mb_{m - 1}\cdots b_1$，其中$b_m = 1$是$k$二进制表示中最高位的$1$。因为$k\neq0$，至少存在一个$SG(v_i)$，其二进制表示的第$m$位是$1$。不妨设这个$i$为$1$（不失一般性），即$SG(v_1)$的二进制表示的第$m$位是$1$。

对于任意整数$x$，$0\leq x < k$，将$x$的二进制表示与$k$的二进制表示进行对比。设$x$的二进制表示为$x = c_mc_{m - 1}\cdots c_1$。
考虑从$v_1$转移到某个后继状态$u_1$，使得$SG(u_1)=SG(v_1)\oplus(k\oplus x)$。因为$k\oplus x < k$（由于$x < k$），所以$SG(u_1)=SG(v_1)\oplus(k\oplus x)$是一个小于$SG(v_1)$的值，在局面$G_1$中一定存在这样的后继状态$u_1$。
此时，新的$SG$​值异或和为：
$$ \begin{align*} SG(u_1)\oplus SG(v_2)\oplus\cdots\oplus SG(v_n)&=(SG(v_1)\oplus(k\oplus x))\oplus SG(v_2)\oplus\cdots\oplus SG(v_n)\\ &=(k\oplus(k\oplus x))\\ &=x \end{align*} $$
这样就证明了对于任意的$x$，$0\leq x < k$，可以通过在某个独立局面中选择合适的后继状态，使得新的$SG$值异或和等于$x$，即能取到$0$到$k - 1$之间的任意值。

回到本题

这样一来就很简单了，当一个局面拆分成两个局面，也就是从$1$个独立局面的组合游戏变成了$2$个独立局面的组合游戏，我们可以根据$SG$函数的定义来进行计算。

#include <cstring>
#include <iostream>
#include <unordered_set>

const int N = 110;

int n, f[N];

int SG(int x)
{
    if (f[x] >= 0) return f[x];

    std::unordered_set<int> hs;
    for (int i = 0; i < x; i++)
        for (int j = 0; j <= i; j++)
            hs.insert(SG(i) ^ SG(j));

    for (int i = 0; ; i++)
        if (!hs.count(i))
            return f[x] = i;
}

int main()
{
    memset(f, -1, sizeof f);

    std::cin >> n;
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int x; std::cin >> x;
        res ^= SG(x);
    }

    std::cout << (res ? "Yes" : "No") << '\n';

    return 0;
}