[LOJ10242] 「一本通 6.7 例 2」取石子游戏 2

Description

ICG 游戏，有 (n) 堆石子，数量分别为 (x_1,x_2,...,x_n)，每次操作选一堆，并从这堆中取走若干石子但不能不取，取走最后一颗石子的人胜利。问先手是否有必胜策略。

Solution

根据 SG 定理，我们只需要将每一个独立游戏（即每一堆）的 SG 值异或起来，即可得到合游戏的 SG 值。

对于每一堆，用石子个数 (n) 作为游戏的状态，则很容易导出 (SG(x)=x)。

即，先手有必胜策略当且仅当 (oplus_{i=1}^n x_i eq 0)。

#include <bits/stdc++.h>
using namespace std;
int n,x;
signed main()
{
    cin>>n;
    while(n--)
    {
        int t;
        cin>>t;
        x^=t;
    }
    cout<<(x?"win":"lose");
}