分析 > 题目：地上有 NNN 堆石子（第 iii 堆石子的数量为 aia_iai ），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如 FM 是先手，且告诉你这 NNN 堆石子的数量，他想知道是否存在先手必胜的策略。若 FM 必败，则额外算出若添加一堆石子可以使 FM 必胜，那么这堆石子的数量 aN+1a_{N+1}aN+1 至少是多少。 如果学过，肯定能一眼看出这是一道经典的 Nim 博弈题目。 Nim博弈的胜负由所有堆石子数的异或和 sumsumsum 决定： * 若 sum=a1⊕a2⊕⋯⊕aN≠0sum = a_1 \oplus a_2 \oplus \dots \oplus a_N \neq 0sum=a1 ⊕a2 ⊕⋯⊕aN =0，先手可通过策略（从某堆取走若干石子，使新的异或和为 000）保证必胜； * 若 sum=0sum = 0sum=0，无论先手如何取，后手都能将异或和重新变为 000，因此先手必败。 当 sum=0sum = 0sum=0（先手必败）时，添加一堆石子 aN+1a_{N+1}aN+1 需满足：新的异或和 new=sum⊕aN+1≠0new= sum \oplus a_{N+1} \neq 0new=sum⊕aN+1 =0。 由于原 sum=0sum = 0sum=0，因此 new=0⊕aN+1=aN+1new = 0 \oplus a_{N+1} = a_{N+1}new=0⊕aN+1 =aN+1 。要使 new≠0new \neq 0new=0 且 aN+1a_{N+1}aN+1 最小，故取 aN+1=1a_{N+1} = 1aN+1 =1（111 是最小的正整数，且 1≠01 \neq 01=0 ）。 关于更多有关 Nim 博弈的知识，可以前往 OI Wiki 查阅，这里不过多介绍。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2025 年 09 月 07 日 版本 1

D. STONE SUBTASK 100 PT 学过的同学一眼看出：这是Nim博弈。没错，这是一道很模板的 Nim 游戏。但是如果 FM 处于必败态时，第 aN+1a_{N+1}aN+1 堆石子数量应该是多少呢？ 众所周知：0⊕1=10\oplus1=10⊕1=1，处于必败态的 FM Nim 和为 000，那么下一堆石子只需要 111 即可。 拓展：Nim 游戏的博弈图和状态。 如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。 例如，如果节点 i,j,k{i,j,k}i,j,k 表示局面为 i,j,ki,j,ki,j,k 时的状态，则我们可以画出下面的博弈图（由于篇幅有限，故仅显示部分状态节点和部分边)： 定义必胜状态为先手必胜的状态，必败状态为先手必败的状态。 通过推理，我们可以得出下面三条定理： * 定理 1：没有后继状态的状态是必败状态。 * 定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。 * 定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。 对于定理 1，如果游戏进行不下去了，那么这个玩家就输掉了游戏。 对于定理 2，如果该状态至少有一个后继状态为必败状态，那么玩家可以通过操作到该必败状态；此时对手的状态为必败状态——对手必定是失败的，而相反地，自己就获得了胜利。 对于定理 3，如果不存在一个后继状态为必败状态，那么无论如何，玩家只能操作到必胜状态；此时对手的状态为必胜状态——对手必定是胜利的，自己就输掉了游戏。 如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用 O(N+M)O(N+M)O(N+M) 的时间（其中 NNN 为状态种数，MMM 为边数)得出每个状态是必胜状态还是必败状态。 AC CODE 时间复杂度：O(T×N)O(T \times N)O(T×N)