Nim博弈模版
![image]()
n个数，Alice和Bob交替取数，Alice先手，每次必须选择一个数取走至少为1的正整数，没有数可取的人输掉比赛。
结论：所有数字的异或和为0时，为必败态；所有数字的异或和不为0时为必胜态。
那么如何去理解这个呢？首先，我们定义异或和为0为状态0异或和非0为状态1，同时用k来表示状态1下所有数的异或和的最高位1的位置。进一步分析，我们可以发现在1状态时一定会存在奇数个 数的第k个二进制位为1，而我们让其中一个数去异或所有数的异或和之后，这个数本身肯定是会减小的，因此是符合游戏规定的操作，在我们进行这个操作之后，所有数的异或和在原本的基础上多异或了一遍他本身。因此状态1必定可以通过一次操作转化为状态0.
而状态0不管如何减少，都会转化为状态1.最终0的状态也为状态0.
由此，当我们先手拿到的是状态1，我们就可以保证对方拿到的是状态0，我方拿到的永远是状态1，进而保证必胜。相对的，如果拿到了状态0，我们是必败的。
Nim博弈变式
2026ICPC南昌邀请铜牌题
我们再来看这题。本题在Nim博弈的基础上多加了一个操作叫做k的限制，即每次减少的数必须<=k直到最终状态为0.
本质上 状态0必定会在一次操作后变为状态1这个条件不会发生任何改变，而k就限制了状态1是否能变成状态0:。
尝试发现k=1的情况是平凡的，如果当前总和为奇数必胜，偶数必败。当k>=2时如果你拿到了总和为奇数的情况时就可以让k=1.此时回到了必胜态。因此双方的最优策略一定是给对方总和为偶数的状态，此时我们每次只会选偶数去减，直到不得不选1.但是偶数的选择是多种多样的，我们很难在原数组的情况下去操作和计算，此时我们需要再次考虑转化。因为每次都只能选偶数，我们可以把它转化为选择一个数 x满足1<=x<=k/2.同时，所有的数也都可以对2向下取整。这样就转化为一个子问题：
在所有ai/2的数组中选择x使得该数组全部为0.
如果向下整除后a数组的和仍为偶数且k仍不为1时就可以一直转化直到k=1或者a数组的和变为奇数。因为k=1的情况是平凡的，因此我们对a数组的和变为奇数的情况做思考。如果a数组的和变为奇数的话，此时新k就可以取1这个子问题就出现了必胜态（Nim博弈结论）。进一步转化后，疑惑和的最低位1的位置就是最小的t使得子问题出现必胜态。
因此只要比较异或和的最低位1和k的大小即可确定胜负。如果k是要大于异或和最低位1所表示的数的（如：异或和10100就是100（4），如果k>=4，则必胜，否则必败）。总结来看代码相当简单，25行不到，但是相当难想。
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){int n,k;cin>>n>>k;int x=0;for(int i=1;i<=n;i++){int y;cin>>y;x^=y;}if(x!=0 && (x&-x)<=k)cout<<"Alice";else cout<<"Bob";cout<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--)solve();
}
台阶型Nim博弈
![image]()
跟Nim博弈不同的是，本题一次操作并不会把一堆里的部分数直接删除，而是放到下一阶梯的数上。我们可先模仿Nim博弈本身的实现思路：发掘最终状态可能的性质，并且该性质可以在一次操作之后必然不存在，并且可以在不存在的状态下经过一次特定操作使其又回到原来的状态。先给出最终结论：
当奇数位上的数异或和不为0时，先手必胜；否则，先手必败。
因为如果奇数位上的数异或和为0时，经过一次随意的操作可以使其必然不为0，而如果异或和不为0时，经过一次特定的操作可以使其必然为0。
那么偶数位上的数异或和不为0时（除了第0位）能否构成必胜态呢？答案是不行的，因为0号位是基底。当一方在从偶数位拿一部分石子放在奇数位时，另一方可以将其直接下沿到下一个偶数位，继续保持奇数位的异或和为0，但当一方从奇数位拿一部分石子放在偶数位时，另一方不能将其直接下沿到下一个奇数位进而保证偶数位异或和为0，因为如果把1阶梯的数放在0阶梯，那就不能下放了。
具体地：
1.假设当前偶数层（如第2层）有石子，奇数层（第1层）异或和为0（必败态）。
2.若先手从第2层移动c个石子到第1层，则第1层石子数增加，奇数层异或和变为非0，看似给对手一个“必胜态”。
3.但后手可以立即将这个石子从第1层全部移到第0层（因为第1层是奇数层，可以向下移动）。这样第1层石子数恢复原状，奇数层异或和回到0，且第2层减少了c。
4.因此，后手总能通过“反弹”操作，保持奇数层的异或和不变（即保持必败态），同时逐步消耗偶数层的石子。最终，偶数层的石子会全部被推入地面，而奇数层始终为0，后手获胜。相反，如果奇数层异或和为0，先手从奇数层移动石子到地面（第0层），则奇数层异或和变为非0，但后手无法从地面再向上移动石子，所以这个影响无法被抵消。因此奇数层的异或和才是真正的胜负判据。
后记
Nim博弈所带来的启发：发掘最终状态可能的性质，并且该性质可以在一次操作之后必然不存在，并且可以在不存在的状态下经过一次特定操作使其又回到原来的状态。
其实Nim博弈中的异或和思想是SG定理中的一个特例。可以将其推广到任意的公平组合游戏：计算每个状态的Grundy数，必败态即Grundy=0的状态。如果游戏能分解为独立子游戏，则总Grundy=子游戏Grundy的异或和。如果游戏不能分解，则仍可递归计算整个状态的Grundy数（例如通过DP或记忆化搜索）。
之后如果有时间我会进行更深入的研究
