AcWing 893. 集合-Nim游戏

题目链接：点击这里

假设只有一堆石子 数量为 $10$10，集合 $S=\left\{ 2,5 \right\}$S={2,5}，其有向图的SG函数值如下，得 $SG(10)=1$SG(10)=1

每一堆石子都按此计算，推广到 $n$n 堆石子：

1. 如果 $SG(G_1​)⊕SG(G_2​)⊕…⊕SG(G_n​)等于0$SG(G1​​)⊕SG(G2​​)⊕…⊕SG(Gn​​)等于0，先手必败
2. 如果 $SG(G_1​)⊕SG(G_2​)⊕…⊕SG(G_n​) 大于0$SG(G1​​)⊕SG(G2​​)⊕…⊕SG(Gn​​)大于0，先手必胜

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_set>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int s[N], f[M];

// 记忆化搜索
int sg(int x)
{
    if(f[x] != -1)  return f[x];
    
    unordered_set<int> st;
    for(int i = 0; i < m; ++i)
    {
        int t = s[i];
        if(x >= t)  st.insert(sg(x - t));
    }
    
    for(int i = 0; ; ++i)
        if(!st.count(i))
            return f[x] = i;
}

int main()
{
    memset(f, -1, sizeof f);
    
    scanf("%d", &m);
    for(int i = 0; i < m; ++i)  scanf("%d", &s[i]);
    
    scanf("%d", &n);
    
    int res = 0;
    for(int i = 0; i < n; ++i)
    {
        int x;
        scanf("%d", &x);
        res ^= sg(x);
    }
    
    if(res)    puts("Yes");
    else    puts("No");
    
    return 0;
}