SG 函数

先定义，SG 函数对应有向无环图（DAG）上的一种游戏：有一枚棋子在起点上，每次可以沿着边往后移动，谁无法移动谁就输了。

公平组合游戏可以转换成他，只需要将局面中的所有状态看成一个节点，合法行动看成有向边。

判断必胜需要求解的就是起点的 SG。

对于终点（没有出边），\(SG=0\)。

对于其他点 \(u\)，设它的出去的点为 \(v\)，则 \(SG(u)=mex(SG(v_1),SG(v_2),\dots)\)。

\(mex\) 表示没有出现的最小自然数，如 \(mex(2,3)=0,mex(1,0)=2,mex(0)=1\)。

然后对于起点，若 \(SG=0\) 必败，反之必胜。

证明：

全 \(0\) 局面 \(SG=0\) 先手必败。
对于当前局面若 \(SG\neq0\)，那么说明可以到达 \(0\)，走到 \(SG=0\) 的点上，那么抛给对手就是 \(SG=0\)。
若 \(SG=0\),说明无法到达 \(0\)，那么只能给对手 \(SG\neq 0\)。

若先手局面为 \(SG\neq 0\)，那么他可以给对手为0，然后对手只能给他非0，最后对手肯定得到全0，必败，先手必胜。

反之，若为0，那么他只能给对手非0，对手给他0，最后他肯定得到全0，必败，后手必胜。

那有的同学肯定好奇：SG为什么不直接取0/1？

那是因为可能会出现多张有向图的情况，此时的结论同 nim：将各SG异或，如果为0，先手必败，否则必胜。

设总值为 \(x\)。

证明分三步，类似于 nim：

全 \(0\) 局面 \(x=0\) 先手必败。
对于当前局面若 \(x\neq0\)，存在某种方式将其变为 \(0\)：

考虑 \(x\) 的最高的为 \(1\) 二进制位（记为 \(k\)），原序列中肯定有至少一个（奇数个）图的SG第 \(k\) 位为 \(1\)。（设为 \(a_i\)）所以 \(a_i\oplus x<a_i\)（前面的位保持不变，然后第 \(k\) 位变为 \(0\)，后面就算均增加也会减少）。那么由于 \(mex=a_i\) 时可以走到 \([1,a_i)\)，所以，让这个有向图走到 \(SG=a_i\oplus x\) 的点上。那么新的异或值就是 \(\oplus_{i=1}^n a_i\oplus x=x\oplus x=0\)，抛给对手一个 \(x=0\) 的局面。
对于当前局面若 \(x=0\)，不存在任何方式将其变为 \(0\)：

用反证法，假设存在某种方式，且走动的记为 \(a_i\)，那么有 \(\oplus_{j=1}^n a_i=0\)，且 \(\oplus_{j=1}^{i-1} a_j\oplus a_i'\oplus_{j=i+1}^{n} a_j=0\)，两个式子异或，其余的数都消去，剩下 \(a_i\oplus a_i'=0\)，即 \(a_i=a_i'\)，而 mex 定义为没有出现过的最小者，只能走到 \([1,a_i)\)，矛盾，所以不存在。

而当先手的局面 \(x>0\) 时，可以构造 \(x=0\)，后手又给出 \(x>0\) 的局面，先手再给予 \(x=0\) 的局面 \(\dots\)，后手总是持有 \(x=0\) 的局面，而最终必败状态全 \(0\) 就是 \(x=0\)，所以后手必定会取到，即后手必败。

反之 \(x=0\)，先手不管怎么搞 \(x>0\)，后手再将其变为 \(0\)，所以先手总是持有 \(x=0\) 的局面，而最终必败状态全 \(0\) 就是 \(x=0\)，所以先手必定会取到，即先手必败。

所以，我们只需要计算异或和，判断是否等于零即可。

对于本题，只需要分堆考虑，对于每一堆，只需要将石子个数当作状态，然后考虑集合中可以取的（比如 \(1,2,3\)，那么就向 \(x-1,x-2,x-3\) 连边），求一遍 \(SG\) 即可。

#include<cstdio>
#include<vector>
using namespace std;
const int N=110;
bool st[N];
int k,s[N],n,x,res,f[N*N];
int sg(int x){
    if(f[x])return f[x];
    vector<int>g;
    for(int i=1;i<=k;++i)
        if(x>=s[i])g.push_back(sg(x-s[i]));
    for(int v:g)st[v]=1;
    for(int i=0;;++i)
        if(!st[i]){
            for(int v:g)st[v]=0;
            return f[x]=i;
        }
}
int main(){
    scanf("%d",&k);
    for(int i=1;i<=k;++i)scanf("%d",s+i);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);
        res^=sg(x);
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}

526互联

SG函数

SG 函数