Nim game ladder Nim game and SG function application (set game)

ladder Nim game

Now? , There is one n Stairs of steps , There are several stones on each step , Among them the first i There are... On the steps ai A stone (i≥1).

Two players take turns , Each operation can take several stones from any step and put them into the next step （ You can't stop taking ）.

You can't take the stones on the ground anymore , In the end, those who can't do it are considered failures .

Ask if both of them adopt the optimal strategy , Whether the first is sure to win .

Input format
The first line contains integers n.

The second line contains n It's an integer , Among them the first i An integer represents the th i Number of stones on steps ai.

Output format
If you start first, you will win , The output Yes.

otherwise , Output No.

Data range
1≤n≤105,
1≤ai≤109
sample input ：
3
2 1 3
sample output ：
Yes

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
    
        int x;
        cin>>x;
        if (i%2) res^= x;
    }
    if (res) cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    return 0;
}

aggregate Nim game

Given n A pile of stones and a pile made of k A number set of different positive integers S.

Now there are two players taking turns , Each operation can take stones from any pile of stones , The number of stones taken each time must be included in the set S, In the end, those who can't do it are considered failures .

Ask if both of them adopt the optimal strategy , Whether the first is sure to win .

Input format
The first line contains integers k, Represents a set of numbers S Number of numbers in .

The second line contains k It's an integer , Among them the first i An integer represents a set of numbers S No i Number si.

The third line contains integers n.

The fourth line contains n It's an integer , Among them the first i An integer represents the th i The number of stones hi.

Output format
If you start first, you will win , The output Yes.

otherwise , Output No.

Data range
1≤n,k≤100,
1≤si,hi≤10000
sample input ：
2
2 5
3
2 4 7
sample output ：
Yes

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N = 1e4+10;
int a[110],f[N];
int n,k;
int SG (int x)
{
    
    if (f[x]!=-1) return f[x];
    unordered_set<int> mh;
    for (int i=0;i<k;i++)
    {
    
        int j = a[i];
        if (x>=j) mh.insert(SG(x-j));
        
    }
    for (int i=0;;i++)
       if (!mh.count(i)) return f[x]=i;
}
int main(){
    
    ios::sync_with_stdio(false);
    cin>>k;
    for (int i = 0; i < k; i ++ ) cin>>a[i];
    cin>>n;
    memset(f, -1, sizeof f);
    int res = 0;
    while (n -- )
    {
    
        int x;
        cin>>x;
        res^=SG(x);
    }
    if (res) cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    return 0;
}

Split -Nim game

Given n Rubble , Two players take turns , Each operation can remove a pile of stones , Then put in two smaller piles of stones （ The new heap size can be 0, And the total number of stones in the two new piles can be greater than the number of stones taken away ）, In the end, those who can't do it are considered failures .

Ask if both of them adopt the optimal strategy , Whether the first is sure to win .

Input format
The first line contains integers n.

The second line contains n It's an integer , Among them the first i An integer represents the th i The number of stones ai.

Output format
If you start first, you will win , The output Yes.

otherwise , Output No.

Data range
1≤n,ai≤100
sample input ：
2
2 3
sample output ：
Yes

666

Compared to the set -Nim, Each pile here can be changed into two piles of any size no larger than the original pile
namely a[i]a[i] Can be broken down into (b[i],b[j])(b[i],b[j]), To avoid repetition b[i]>=b[j]b[i]>=b[j], namely ：a[i]>=b[i]>=b[j]a[i]>=b[i]>=b[j]
It is equivalent to splitting one situation into two situations , from SG Function theory , Multiple independent situations SGSG value , Equal to these situations SGSG The XOR and of values .
So the state that needs to be stored is sg(b[i])sg(b[i])^sg(b[j])sg(b[j])（ And assemble -Nim The only difference ）

#include <iostream>
#include <cstring>
#include <algorithm>
#include<unordered_set>
using namespace std;
const int N = 110;
int a[N],f[N];
int n;
int sg(int x)
{
    
    if (f[x]!=-1) return f[x];
    unordered_set<int> mh;
    for (int i=0;i<x;i++)
        for (int j=0;j<=i;j++)
        mh.insert(sg(i)^sg(j));
        
    for (int i=0;;i++)
    if (!mh.count(i)) return f[x] = i;
}
int main()
{
    
    ios::sync_with_stdio(false);
    memset(f, -1, sizeof f);
    cin>>n;
    int res = 0;
    for (int i = 0; i < n; i ++ ) {
    
        cin>>a[i];
        res^= sg(a[i]);
    }
    if (res) cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    return 0;
}