#创作计划# Nim游戏大学习

KID2695

2025-10-23 15:41:27

发布于：山东

7阅读

0回复

0点赞

Nim 游戏总集

Nim和：所有元素的异或和

Nim

基础形式： $n$ 堆物品，每堆 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜
结论：当且仅当Nim和为0时，先手必败，反则先手必胜
证明：
- 发现最终局面是没有任何石子，先手必败，满足性质Nim和为0，所有Nim和为0的局面一定只能转移到Nim和不为0的局面（我们为了行文方便，称之为性质1），所有Nim和不为0的局面只能转移到Nim和为0的局面（我们称之为性质2）。
- 性质1的证明：考虑反证法，如果可以找到一堆石子，然后移除部分石子让异或和不变，那意味着我们取出的这个数量在二进制下的每一位都是0，相当于我们没有取石子，所以实现不了，故性质1成立。
- 性质2的证明：这里可能比较难理解，我们干脆直接给出玩家该如何具体操作来证明这个性质吧，玩家先找到石子最多的一堆，然后发现这一堆的石子数一定大于其它石子堆的异或和，因为这一堆石子数量最多，所以总的异或和二进制里的最高位一定由这一堆石子数来提供，相当于说明了这一堆的石子数一定大于其它石子堆的异或和，又由于两个相同数的异或和为零，我们只需要把这一堆石子也取到其它石子堆的异或和的数量，总的异或和就为0了。
题目：
- P2197 【模板】Nim 游戏
  - 模板，略
- P1247 取火柴游戏
  - 找每个元素让Nim和变为0需要操作的最小数即可
- P7589 黑白棋（2021 CoE-II B）
  - 显然我们把每条线上的两点间的距离看作一堆石子，很像Nim游戏
  - 考虑加石子的操作，因为有限，所以后手加石子的时候先手直接取走对应数量的石子就行了，这时候局面未变
  - 综上，直接走Nim游戏就行了
- P5675 [GZOI2017] 取石子游戏
  - 根据Nim游戏的结论我们有以下结论
    - <1>所有石子堆的Nim和为0，先手必输
    - <2>如果指定的那一堆没法通过取石子让Nim和变为0，先手必输
  - 对于<2>很困难，我们正难则反，考虑什么情况能让<2>被打破
    - 假设第i堆石子取走k个厚Nim和为0，其余堆的异或和为b，则 $(a_i-k)\oplus b=0$
    - 这个式子等价于 $a_i-k=b$ ，即 $a_i-b>0$
  - 那么对于满足<2>的我们枚举i后求出其它堆的异或和大于等于 $a_i$ 的方案数即可

阶梯Nim

基础形式：有 $n$ 堆石子，每堆石子的数量为 $x_1,x_2,\dots,x_n$ ，A与B轮流操作，每次可以选第 $k$ 堆中的任意多个石子放到第 $k-1$ 堆中，第1堆中的石子可以放到第0堆中，最后无法操作的人为输。问 A先手是否有必胜策略。
结论：先手必败当且仅当奇数堆中的石子数异或和为0
证明：
- 显然先手如果不能让奇数堆的Nim和变为0的唯一方案就是所有石子都在0点上，此时已输
- 如果移动石子让奇数堆的Nim和变为0则有两种情况
  - <1>操纵的是奇数堆
    - 后手一定能移动某一个奇数堆的若干石子往下一个堆使得奇数堆的Nim和变回0
  - <2>操纵的是偶数堆
    - 后手把这些操作的石子全部往下移一个堆就能让奇数堆的Nim和变回0
- 另一方面，如果最开始奇数堆的Nim和不为0，那么先手一定能一步让这些奇数堆的Nim和变为0，但此时先后手已经交换了，故必胜
题目：
- P3480 [POI 2009] KAM-Pebbles
  - 显然任何时刻的差分数组非负，移动石子可以看作差分数组上的移动，变为差分数组上的倒着的阶梯Nim了
- P2575 高手过招
  - 发现有若干子游戏互不相关，直接拆开，最后用SG定理合起来
  - 现在把棋子的连续段缩成一堆石子，空位就算0石子堆，变味了阶梯Nim，注意这个阶梯Nim依旧是倒着的

Anti Nim

基础形式： $n$ 堆物品，每堆 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人失败
结论：
- <1>所有堆的石子数均为1且为偶数堆，先手必胜
- <2>至少有一堆石子个数大于1且Nim和不为0，先手必胜
- <3>否则先手必输
证明：
- <1>的正确性显然
- 当只有一堆石子数大于1，显然此时Nim和不为0
  - 如果堆数为奇数，则把多的那一堆取到剩一个，显然后手必输，先手必胜。
  - 如果堆数为偶数，则直接取走多的那一堆，显然后手必输，先手必胜。
- 当有两堆及以上的石子数大于1时
  - 当Nim和为0时，显然会转移到Nim和非0的情况，如果石子数大于1的堆的数量变为了1，那么显然先手必输，否则会变为下面的情况。
  - 当Nim和不为0时，显然可以转移到Nim和为0的情况，也就是上面那种情况，显然先手必胜，后手必输。
题目：
- P4279 [SHOI2008] 小约翰的游戏
  - 模板，略

K-Nim

基础形式：有 $n$ 堆石子，其中第 $i$ 堆有 $a_i$ 颗，每次可以取走1至k堆石子中任意颗石子，不能操作者输
结论（记数字 $x$ $x$ 在二进制下的第 $i$ $i$ 位表示为 $(x)_i$ $(x)_{i}$ ）：
- 若 $\forall s,(\sum\limits_{i=1}^n(a_i)_s)\mod (k+1)=0$ ，则先手必败，反之先手必胜。
证明：
- 终止状态为必败状态（P态）
  - 所有石子堆为0，满足
- 所有P态只能转移到N态
  - 因为最多操作k堆石子，但是要让mod(k+1)依旧是0需要至少k+1次操作。故P状态转移到的状态不是P态，即N态。
- 所有N态可以转化到P态
  - 显然只需要按位拿就行了
- 显然性质成立
题目：
- P2490 [SDOI2011] 黑白棋
  - 显然最终局面是这些棋子黑白棋子交错的堆在一起
  - 我们把相邻两个棋子（左白右黑）间的距离看作一堆石子，问题就成了d-Nim游戏的必胜局面方案数了
  - 考虑前i个二进制都为0且用掉了j个位置的方案数，这里实际记录的是非法的，最后要用 $(_k^n)$ 减一下
  - $dp_{i+1,j+t \times (d+1) \times 2^i} \leftarrow dp_{i,j} \times \binom{\frac{k}{2}}{t \times (d+1)}$
  - 答案就是 $(_k^n)-\sum_{i=1}^{n-k} dp_{maxl+1,i} \binom{n-i-\frac{k}{2}}{\frac{k}{2}}$

Fibonacci Nim

基础形式：
结论：
- <1>如果n为斐波那契数，则先手要全取走
- <2>如果正整数 n 不为斐波那契数，则将其用齐肯多夫表示法表示后，最小的那一堆个数即为答案
证明
- <1>不妨设 $n=Fbi_i=Fbi_{i-1}+Fbi_{i-2}$ $n = F b i_{i} = F b i_{i - 1} + F b i_{i - 2}$
  - 如果先手不取 $Fbi_i$ $F b i_{i}$ ，那么有一下两种情况
    - 取了一个大于 $Fbi_{i-2}$ $F b i_{i - 2}$ 的数
      - 显然 $Fbi_i<3Fbi_{i-2}$
      - 所以后手能一步制胜
    - 取了一个小于 $Fbi_{i-2}$ $F b i_{i - 2}$ 的数
      - 显然这个数要是斐波那契数，原因见结论<2>的证明
      - 显然后手可以一步把这个数保持成一个斐波那契数
      - 我们考虑极端的末尾情况，n=2（显然n=1全取走，意义不大）
        
        先手不取2的话只能取1，后手取1赢
      - 所以我们可以归纳的证明出结论<1>
- <2>根据齐肯多夫定理，我们可以把n表示为 $f_1+f_2+\dots+f_k$ $f_{1} + f_{2} + \dots + f_{k}$ 满足 $\forall i，f_i为斐波那契数。f_1<f_2<\dots<f_k$ $\forall i ， f_{i} 为斐波那契数。 f_{1} < f_{2} < \dots < f_{k}$
  - 先手先取 $f_1$ ，显然后手没法一步取走 $f_2$ ，因为 $f_2>2f_1$ 一定存在
  - 我们假设先手足够聪明，那么先手一定可以通过拉扯来作为取走属于 $f_2$ 的最后一个元素
  - 同理我们对于每一个 $f_i$ 最后的一个元素都是先手取走的，所以最后是先手赢
  - 现在的问题是为什么这个值是最小的
  - 如果存在更小值，那么这个值一定小于 $\dfrac{f_1}{2}-1$ ，不然后手就能用上面的规律获胜了。更进一步，按上述规律一定能找到一个更小的斐波那契数，但是并没如，所以这个数最小。

例题：

P6487 [COCI 2010/2011 #4] HRPA
- 模板，略。

P6791 [SNOI2020] 取石子

可以让 $n$ 减小1，因为显然多取一个不会犯规，这样Anti Nim就解决了
然后现在就是再求有多少数按贪心的构造下最小的斐波那契数小于了k，由于不会有两项相邻的斐波那契数加入构造，直接dp就行，细节间代码吧，dp写多了觉得应该都不算细节

ll wk(int p,bool pre,bool lst){
	if(p<k) return 1;
	if(!pre&&!lst&&dp[p]!=-1) return dp[p];
	ll res=0;
	res+=wk(p-1,pre&(vis[p]==0),0);
	if(!lst&&(!pre||vis[p]==1)){
		res+=wk(p-1,pre,1);
	}
	if(!lst&&!pre) dp[p]=res;
	return res;
}
signed main(){
	f[1]=1;
	f[2]=2;
	FOR(i,3,90) f[i]=f[i-1]+f[i-2];
	while(t--){
		k=iread();
		n=iread();
		--n;
		ll jn=n,jk=k;
		memset(vis,0,sizeof vis);
		RFOR(i,90,1){
			if(f[i]>jk){
				k=i;
			}
		}
		RFOR(i,90,1){
			if(jn>=f[i]){
				jn-=f[i];
				vis[i]=1;
			}
		}
		memset(dp,-1,sizeof dp);
		printf("%lld\n",n-wk(90,1,0)+1);
	}
	return 0;
}

课后作业

如果P态（或N态）满足了一个性质q，并且所有满足性质q的局面只能转移到不满足性质q的局面，但所有不满足性质q的局面都可以转移到满足性质q的局面，那就可以通过看初始局面是否满足q性质来判断先手是否必胜
这个也可以用于证明
试着用这个去证明一下上面的所有Nim游戏吧

有帮助，赞一个

去预览

0/2000

全部评论 1

KID2695
齐肯多夫（Zeckendorf）定理

内容：任何正整数都可以表示成若干个不连续的斐波那契数之和

这种和式称为齐肯多夫表述法

构造这种和式可以通过每次贪心选出最大的不超过它的斐波那契数

证明：

这里只考虑 $n$ 不为斐波那契数的情况

定理证明

考虑数学归纳法，可以无脑得到 $1=1,2=2,3=3,4=1+3,5=2+3\dots$

假设现在所有小于 $n$ 的数都满足该定理，那么我们选择让 $n$ 减去最大的不超过它的斐波那契数，显然新的 $n$ 小于了旧的 $n$ ，故满足，至于为什么不会选重斐波那契数见下文

构造证明

考虑我们依次取 $Fib_{t_1}\leqslant n<Fib_{t_1+1},Fib_{t_2}\leqslant n-Fib_{t_1}<Fib_{t_2+1}$

显然， $t_1\not=t_2$ ，因为 $2Fib_{t_1}\geqslant Fib_{t_1}+Fib_{t_1-1}=Fib_{t_1+1}>n$
3天前来自山东
0

Nim 游戏总集

Nim

阶梯Nim

Anti Nim

K-Nim

Fibonacci Nim

课后作业

全部评论 1

齐肯多夫（Zeckendorf）定理

热门讨论