当前位置：首页 > news >正文

Nim

news 2026/4/25 17:17:35

Nim

题目
题意
$n$堆石子，每堆$a_i$个，每人每次可从任意一堆石子中取任意多个石子，可以取完，但不能不取。
每次只能从一堆里取，取走最后一枚的人获胜。
做法
定义$Nim$和为$a_1\oplus a_2\oplus \dots \oplus a_n$
当且仅当$Nim$和为$0$时，先手必败，否则先手必胜。
证明
由
- $Nim$和为$0$时状态一定没有$Nim$和为$0$的后继状态。
  证明
  反证法，设将$Nim$和为$0$状态下的$a_i$改为$a_i'$（$a_i\neq a_i'$），$Nim$和仍为$0$。
  则$a_1\oplus a_2\oplus\dots\oplus a_i\oplus\dots\oplus a_n=0=a_1\oplus a_2\oplus\dots\oplus a_i'\oplus\dots\oplus a_n$。
  
  可得$a_i=a_i'$，与假设矛盾，故原命题成立。
- $Nim$和不为$0$时状态一定有$Nim$和为$0$的后继状态。
  证明
  设当前状态下$Nim$和为$k$。
  若要将$Nim$和变为$0$，则需要将$a_i$变为$a_i\oplus k$.
  
  因为在$k$在二进制下的最高位上，有奇数个$1$。所以若$a_i$在这一位上为$1$，则$a_i\geq a_i\oplus k$ ，也满足石子越取越少的条件。
可得
- 没有后继状态的状态一定是必败状态。
- 一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
- 一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

阶梯Nim

题目
目前没有找到模板题。
题意
$n$堆石子，每堆$a_i$个，每人每次可从任意一堆石子中取任意多个石子放入左边的那一堆，可以取完，但不能不取。
每次只能从一堆里取，将最后一枚放入第$0$堆的人获胜。
做法
当且仅当奇数堆中的石子数异或和为$0$，先手必败，否则先手必胜。
证明
第一步，先手先将奇数堆的$Nim$和变为$0$。如果不能则必败。
若后手移动奇数堆，则将奇数堆的$Nim$和重新变为$0$。
若后手移动偶数堆，则将后手移动到奇数堆的石子移至下一个偶数堆。
多次操作后，先手总能保证奇数堆处于必胜状态，总可以在后手之后将石子从奇数堆移动到偶数堆，最后移动到$0$堆。

例题

[POI 2009] KAM-Pebbles
差分，转化为反向阶梯Nim。

高手过招
每行单独处理，最后亦或起来即可。

int anss=0;
while(n--){for(int i=1;i<=20;i++)	vis[i]=0;//初始均无棋子int cnt0=21-m,//空格总数（加上棋盘最右边）cnt1=0,//连续棋子的个数ans=0;//当前行的阶梯Nim异或和while(m--){int x;cin>>x;vis[x]=1;//标记x列有棋子}for(int i=1;i<=20;i++){if(!vis[i]){//当前位置是空格cnt0--;//剩余空格数-1if(cnt0&1)	ans^=cnt1;//奇数个空格时，异或上一段连续棋子数cnt1=0;//重置连续棋子数}else	cnt1++;//当前位置有棋子，连续棋子数+1}anss^=ans;
}
if(anss)	cout<<"YES\n";
else	cout<<"NO\n";

Anti Nim

题目
目前没有找到模板题。
题意
$n$堆石子，每堆$a_i$个，每人每次可从任意一堆石子中取任意多个石子，可以取完，但不能不取。
每次只能从一堆里取，取走最后一枚的人失败。
做法
- 若所有堆的石子数均为$1$且$Nim$和为$0$，先手必胜。
- 若至少有一堆石子个数大于$1$且$Nim$和$\neq 0$，先手必胜。
- 否则先手必败。
证明
- 第一种情况：
  即$n$为偶数，易知先手必胜。
- 第二种情况：
  若至少还有两堆物品数大于$1$，则先手一定可以将局势变为至少有一堆石子数大于$1$，且$Nim$和为$0$。
  若只有一堆石子数大于$1$，则先手一定可以将局势变为有奇数个$1$。

K-Nim

题目
目前没有找到模板题。
题意
$n$堆石子，每堆$a_i$个，每人每次可从任意$j$堆石子中取任意多个石子（$1\leq j\leq k$），可以取完，但不能不取。
每次只能从一堆里取，取走最后一枚的人胜利。
做法
记$x_i$表示$x$二进制下的第$i$位。若$\forall s,(\sum_{i=1}^n{a_i}_s)\equiv 0(\bmod k+1)$，则先手必败，否则先手必胜。
证明