引子

校赛遇到了一道很经典的$Nim$问题，借此机会严格证明一下。

参考资料

Nim的博弈详解(简单易懂）（一）_nim博弈-CSDN博客

G58 尼姆（Nim）游戏【博弈论】_哔哩哔哩_

Nim游戏

定义

$n$堆物品，每堆有$a_i$个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。

取走最后一个物品的人获胜。

结论

$a_1\bigoplus a_2 \bigoplus \cdots \bigoplus a_n \neq 0$，则先手必胜。

$a_1\bigoplus a_2 \bigoplus \cdots \bigoplus a_n = 0$，则先手必败。

证明

• 博弈论有两种状态，一种为必胜态，一种为必败态。可以得到以下三个命题：1.无法操作的状态为必败态；2.必胜态可以通过某种操作改变为必败态；3.必败态后继状态必为必胜态。满足以上三个命题则可以证明以上结论正确。
• 无法操作的状态为所有物品被取完后的状态，此时$a_i = 0(1 \leq i \leq n)$，所以$0 \bigoplus 0 \cdots \bigoplus 0 = 0$，命题一证毕。
• 如果现在为必胜态，设$s = a_1 \bigoplus a_2 \bigoplus \cdots \bigoplus a_n \neq 0$，设$bins$为$s$的二进制形式，设$bin\_s[j]$为$s$最高位的$1$，$bin\_s[k] = 0(0 \leq k < j)$。则肯定存在奇数个$bin\_a_i[j] = 1$，对于$a_i = a_i \bigoplus s$，$bin\_a_i[k](0 \leq k < j)$保持不变，$bin\_a_i[j]$从$1$变为零，此时$a_i$减少，所以$a_i = a_i \bigoplus s$为合法操作。此时$a_1 \bigoplus a_2 \bigoplus \cdots a_i \bigoplus s \bigoplus \cdots \bigoplus a_n = a_1\bigoplus a_2 \bigoplus \cdots \bigoplus a_n \bigoplus s = s \bigoplus s = 0$，从必胜态转化为必败态，命题二证毕。
• 如果现在为必败态，那么对于每一位二进制位$a$中等于$1$的个数必为偶数。如果改变$a$中任意一个数至少一个二进制上的$1$的个数会从偶数变为奇数，此时$a_1 \bigoplus a_2 \bigoplus \cdots \bigoplus a_n \neq 0$，命题三证毕。

Nim例题

题面

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 512MB，其他语言 1024MB

描述

$Alice$和$Bob$在玩游戏。现有三个整数$a,b,c$，确保存在一个三条边分别为$a,b,c$的非退化的三角形。游戏按如下方式进行：玩家轮流地对$a,b,c$中的某个整数进行减法（减去某个正整数）操作。当边$a,b,c$不再能构成一个非退化的三角形，当前玩家就输了。

$Alice$先玩。如果两个玩家都以最优的策略玩，$Alice$能赢吗？

注：退化三角形是指三角形的三个点在一条直线上。

输入描述

第一行为一个整数$T(1\leq T \leq 10^4)$，表示测试用例数。

对于每个测试用例，输入只有一行三个整数$a,b,c(1 \leq a,b,c \leq 10^9)$。确保存在一个非退化的三角形，它的边分别是$a,b,c$。

输出描述

对于每个测试用例，如果$Alice$能赢，输出一行“Win”，否则输出一行“Lose”。

用例输入 1

3
2 2 3
2 3 4
5 3 4

用例输出 1

Win
Lose
Win

解题思路

• 如果直接把三角形三条边$a,b,c$带入$Nim$游戏的结论，会存在问题。因为$Nim$游戏的必败态为$a \bigoplus b \bigoplus c = 0 \Rightarrow a \bigoplus b = c$，而$a + b \geq a \bigoplus b = c$，可是对于一个三角形三条边$a,b,c$满足$a + b > c$，前式中存在等号因此不成立。
• 此时可以对三条边各减去一个$1$，此时三角形满足$(a - 1) + (b - 1) \geq (c - 1)$，此时必胜态为$(a - 1) \bigoplus (b - 1) \bigoplus (c - 1) \neq 0$，必败态为$(a - 1) \bigoplus (b - 1) \bigoplus (c - 1) = 0$。
• 无法操作的状态为$a = 1,b = c$，此时$(a - 1) \bigoplus (b - 1) \bigoplus (c - 1) \Rightarrow 0 \bigoplus b \bigoplus b = 0$，命题一证毕。
• 命题二三证明同$Nim$游戏的证明。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef double db;

const db PI = acos(-1);
typedef array<ll, 2> PII; // vector<PII> a(n + 1);
const ll inf = 2e18 + 10;
const int mod = 998244353;
const int maxn = 2e5 + 10;
bool multi = 1;

void Solve() {
    ll a, b, c; cin >> a >> b >> c;
    if(((a - 1) ^ (b - 1) ^ (c - 1)) == 0) cout << "Lose\n";
    else cout << "Win\n"; 
}


signed main() {
    // freopen("test.in","r",stdin);  
    // freopen("code.out","w",stdout);    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll T = 1;
    if(multi) cin >> T;
    while(T -- ) {
        Solve();
    }
    return 0;
}