官方题解 | Stone

D. Stone

Subtask 100 pt

学过的同学一眼看出：这是Nim博弈。没错，这是一道很模板的 Nim 游戏。但是如果 FM 处于必败态时，第 $a_{N+1}$ 堆石子数量应该是多少呢？

众所周知：$0\oplus1=1$，处于必败态的 FM Nim 和为 $0$，那么下一堆石子只需要 $1$​ 即可。

拓展：Nim 游戏的博弈图和状态。

如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。

例如，如果节点 ${i,j,k}$ 表示局面为 $i,j,k$ 时的状态，则我们可以画出下面的博弈图（由于篇幅有限，故仅显示部分状态节点和部分边)：

定义必胜状态为先手必胜的状态，必败状态为先手必败的状态。

通过推理，我们可以得出下面三条定理：

• 定理 1：没有后继状态的状态是必败状态。
• 定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
• 定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

对于定理 1，如果游戏进行不下去了，那么这个玩家就输掉了游戏。

对于定理 2，如果该状态至少有一个后继状态为必败状态，那么玩家可以通过操作到该必败状态；此时对手的状态为必败状态——对手必定是失败的，而相反地，自己就获得了胜利。

对于定理 3，如果不存在一个后继状态为必败状态，那么无论如何，玩家只能操作到必胜状态；此时对手的状态为必胜状态——对手必定是胜利的，自己就输掉了游戏。

如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用 $O(N+M)$ 的时间（其中 $N$ 为状态种数，$M$ 为边数)得出每个状态是必胜状态还是必败状态。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int T; cin >> T;
	while(T--){
		int n; cin >> n;
		int ans = 0;
		for(int i = 1;i <= n;i++){
			int t; cin >> t;
			ans ^= t;
		}
		if(ans) cout << "Yes\n";
		else cout << "No 1\n";
	}
    return 0;
}

时间复杂度：$O(T \times N)$