公平組合游戲：
1.由兩名玩家交替行動；
2.在游戲進程的任意時刻，可以執行的合法行動與輪到哪名玩家無關；
3.不能行動的玩家判負；

有向圖游戲：給定一個有向無環圖，圖中有一個唯一的起點，在起點上放有一枚棋子。兩名玩家交替地把這枚棋子沿有向邊進行移動，每次可以移動一步，無法移動者判負。
任何一個公平組合游戲都可以轉化為有向圖游戲。具體方法是，把每個局面看成圖中的一個節點，并且從每個局面向沿著合法行動能夠到達的下一個局面連有向邊。
\(nim\) 游戲屬于公平組合游戲。

在有向圖游戲中，對于每個節點 \(x\)，設從 \(x\) 出發共有 \(k\) 條有向邊，分別到達節點 \(y_1, y_2, ..., y_k\)，定義 \(SG(x)\) 為 \(x\) 的后繼節點 \(y_1, y_2, ..., y_k\) 的 \(SG\) 函數值構成的集合再執行 \(mex(S)\) 運算的結果。
即：\(SG(x) = mex({SG(y_1), SG(y_2), ..., SG(y_k)})\)

nim游戲

lugou：https://www.luogu.com.cn/problem/P2197
acwing：https://www.acwing.com/problem/content/893/

\(n\) 堆石子，兩人依次從任意一堆中取任意個，不能操作的人輸。問先手是否必勝。
當 \(a_1\) ^ \(a_2\) ^ ... ^ \(a_n\) != 0 時，先手必勝。

#include <bits/stdc++.h>
using namespace std;
int T, n;
void solve(){
	cin >> n;
	int k = 0, x;
	for (int i = 1; i <= n; i ++ ){
		cin >> x;
		k ^= x;
	}
	if (k) cout << "Yes\n";
	else cout << "No\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	while ( T -- )
		solve();
	return 0;
}

SG函數

\(SG\) 函數異或值大于 0 則先手必勝。

acwing：https://www.acwing.com/problem/content/895/

\(n\) 堆石子以及一個 \(k\) 個不同整數組成的數字集合 \(S\)。兩個玩家依次操作，每次從任意一堆石子中取集合中一個數個數的石子，不能操作的人輸。問先手是否必勝。

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1e4 + 10;
int n, m, x, ans, s[N], f[M];
int sg(int x){
	if (f[x] != -1) return f[x];
	unordered_set <int> S;
	for (int i = 0; i < m; i ++ ){
		int sum = s[i];
		if (x >= sum) S.insert(sg(x - sum));
	}
	for (int i = 0; ; i ++ )
		if (!S.count(i))
			return f[x] = i;
}
int main(){
	cin >> m;
	for (int i = 0; i < m; i ++ )
		cin >> s[i];
	memset(f, -1, sizeof f);
	cin >> n;
	for (int i = 0; i < n; i ++ ){
		cin >> x;
		ans ^= sg(x);
	}
	if (ans) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

acwing：https://www.acwing.com/problem/content/896/

\(n\) 堆石子，兩個玩家依次取走一堆石子，再放入兩堆數量更小的石子，不能操作的人輸。問先手是否必勝。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int ans, n, f[N], x;
int sg(int x){
	if (f[x] != -1) return f[x];
	unordered_set<int> S;
	for (int i = 0; i < x; i ++ )
		for (int j = 0; j <= i; j ++ )
			S.insert(sg(i) ^ sg(j));
	for (int i = 0; ; i ++ )
		if (!S.count(i))
			return f[x] = i;
}
int main(){
	cin >> n;
	memset(f, -1, sizeof f);
	for (int i = 0; i < n; i ++ ){
		cin >> x;
		ans ^= sg(x);
	}
	if (ans) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}