Game theory acwing 893 Set Nim game

Game theory AcWing 893. aggregate -Nim game

Original link

AcWing 893. aggregate -Nim game

Algorithm tags

Math knowledge Game theory SG function

Ideas

If there is only a pile of stones SG Function calculation

Conclusion

For multiple heaps of stones
SG The value of the function is equal to each sub game it contains SG The exclusive or sum of function values , namely :SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm), if SG(G) by 0, You will win , otherwise , You will lose

Other concepts

Code

#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105, M = 10005;
int s[N], f[M];
int k, n;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
int sg(int x){
	// f[x] Has it been calculated 
    if(f[x]!=-1){
        return f[x]; 
    }else{
    	//  Store the current situation and the situation that can be reached 
        unordered_set<int> S;
        rep(i, 0, k){
            if(x>=s[i]){
                S.insert(sg(x-s[i]));
            }
        }
        //  Find the minimum natural number that does not exist in the set 
        for(int i=0;;++i){
            if(!S.count(i)){
                return f[x]=i;
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    k=read();
    rep(i, 0, k){
        s[i]=read();
    }
    n=read();
    memset(f, -1, sizeof f);
    int ans=0; 
    rep(i, 0, n){
        int x=read();
        ans^=sg(x);
    }
    if(ans){
        puts("Yes");
    }else{
        puts("No");
    }
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support