【题目来源】
AcWing：894. 拆分-Nim游戏 - AcWing题库
【题目描述】
给定 \(n\) 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 \(0\)，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
【输入】
第一行包含整数 \(n\)。
第二行包含 \(n\) 个整数，其中第 \(i\) 个整数表示第 \(i\) 堆石子的数量 \(a_i\)。
【输出】
如果先手方必胜，则输出 Yes。
否则，输出 No。
【输入样例】
2
2 3
【输出样例】
Yes
【算法标签】
《AcWing 894 拆分-Nim游戏》 #数学知识# #博弈论# #SG函数#
【代码详解】
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;const int N = 105; // 最大石子数
int f[N]; // 记忆化SG函数值，f[x]表示有x个石子的SG值// 计算有x个石子的SG函数值
int sg(int x)
{// 如果已经计算过，直接返回记忆化的值if (f[x] != -1){return f[x];}// 存储所有可能分裂后状态的SG值的异或和unordered_set<int> S;// 遍历所有可能的拆分方式// 将x个石子拆分成两堆：一堆i个，一堆j个// 其中 i + j < x（至少剩下1个石子用于拆分）for (int i = 0; i < x; i++) // 第一堆的大小，0 ≤ i < x{for (int j = 0; j <= i; j++) // 第二堆的大小，0 ≤ j ≤ i{// 拆分成两堆(i,j)后，形成两个独立的游戏// 组合游戏的SG值是两个独立游戏SG值的异或S.insert(sg(i) ^ sg(j));}}// mex操作：找到最小的不在集合S中的非负整数for (int i = 0; ; i++){if (!S.count(i)) // 如果i不在集合S中{return f[x] = i; // 记忆化并返回SG值}}
}int main()
{int n; // 石子堆数cin >> n;// 初始化SG函数记忆化数组为-1（表示未计算）memset(f, -1, sizeof(f));int res = 0; // 所有石子堆SG值的异或和// 输入每堆的石子数，并计算SG值的异或和for (int i = 0; i < n; i++){int x; // 当前堆的石子数cin >> x;res ^= sg(x); // 计算当前堆的SG值并异或}// 根据SG定理判断胜负：// 如果所有石子堆SG值的异或和不为0，先手必胜// 如果所有石子堆SG值的异或和为0，先手必败if (res){cout << "Yes" << endl; // 先手必胜}else{cout << "No" << endl; // 先手必败}return 0;
}
【运行结果】
2
2 3
Yes