sg函数(全称Sparague—Grundy)
它是博弈论和组合游戏理论中的一个重要概念,用于分析组合游戏的输赢情况,特别是那些具有明确终止条件和有限状态空间的游戏。
定义
对于一个给定的组合游戏,其sg函数G(n)是一个非负整数,用于表示游戏位置n的"输赢状态";两个游戏位置的sg函数值相同,意味着从这两个位置开始,对于任何一个玩家来说,都存在相同的赢或输的策略。
性质
终止位置:
终止位置的sg函数值通常定义为0(表示当前玩家无法移动,即输掉游戏,但这也取决于具体的游戏规则和胜负判断)
非终止位置:
对于非终止位置n,其sg函数数值G(n)是后续所有可能位置m的sg函数值集合中不包含的最小非负整数(即mex函数)
周期性:
在某些游戏中,sg函数值可能呈现出周期性,这意味着当游戏状态达到某个特定大小时,其输赢情况会开始重复
计算方法
确定终止位置
首先确定所有可能的终止位置,并给它们赋予适当的sg值(通常为0)
逆向递归
从终止位置开始,逆向归纳计算每一个非终止位置的sg值。涉及递归地考虑所有可能的移动和后续位置
应用mex函数
对于每个非终止位置,使用mex函数来找到其sg值。mex函数返回的是不包含在给定集合中的最小非负整数。
示例
给一个简单的Nim游戏的变体:其中有一堆n个石子,两个玩家轮流取,每次可以取1~k个石子,取走最后一个石子的人获胜。这个游戏的sg函数计算:
1、对于n=0,这是一个失败的问题,因为没有石子可以取了,所以G(0)=0(但注意,有些定义中可能不给终止位置赋SG值,或者视为特殊值)。
2、对于n>=0,玩家会尝试取走一定数量的石子,使得剩下的石子数量m的sg函数值G(m)!=0。
3、通过计算可以发现,这个游戏的SG函数值呈现一种周期性模式,即当n足够大时,G(n)的值会开始重复。具体来说,周期的长度通常与k+1有关(但这也取决于具体的游戏规则)。
巴什博弈
题目描述
十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称:zatiura),一直到现在,我依然对于电影中的部分电脑特技印象深刻。
今天,大家选择上机考试,就是一种勇敢(brave)的选择;这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是"勇敢者的游戏”,这也是我命名这个题目的原因。当然,除了“勇敢",我还希望看到"诚信”,无论考试成绩如何,希望看到的都是一个真实的结果,我也相信大家一定能做到的~
各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
1、本游戏是一个二人游戏:
2、有一堆石子一共有n个;
3、两人轮流进行:
4、每走一步可以取走1…m个石子;
5、最先取光石子的一方为胜;
如果游戏的双方使用的都是最优策略,请输出哪个人能赢。
输入
输入数据首先包含一个正整数C(C<-100),表示有C组测试数据。
每组测试数据占一行,包含两个整数n和m(1<-n.m<-1000),n和m的含义见题目描述
输出
如果先走的人能赢,请输出“frst”,否则请输出“second”,每个实例的输出占一行。
输入数据
2
23 2
4 3
输出数据
first
second
题解思路
当m=4时,石头数为0时前者为必胜态,1时也为必胜态,2时也为必胜态,3也为必胜态,4也为必胜态,5也为必败态…,依次类推可以得出当n%(m+1)==0时为必败态。
code:
#include<iostream>
using namespace std;
void solve(){int n,m;cin>>n>>m;if(n%(m+1)) cout<<"first"<<'\n';else cout<<"second"<<'\n';
}
int main(){int n;cin>>n;while(n--){solve();}return 0;
}
尼姆博弈
【模板】Nim 游戏
题目描述
甲,乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的:地上有 n n n 堆石子(每堆石子数量小于 1 0 4 10^4 104),每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取完,不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手,且告诉你这 n n n 堆石子的数量,他想知道是否存在先手必胜的策略。
输入格式
本题有多组测试数据。
第一行一个整数 T T T ( T ≤ 10 T\le10 T≤10),表示有 T T T 组数据
接下来每两行是一组数据,第一行一个整数 n n n,表示有 n n n 堆石子, n ≤ 1 0 4 n\le10^4 n≤104。
第二行有 n n n 个数,表示每一堆石子的数量.
输出格式
共 T T T 行,每行表示如果对于这组数据存在先手必胜策略则输出 Yes
,否则输出 No
。
样例 #1
样例输入 #1
2
2
1 1
2
1 0
样例输出 #1
No
Yes
解题思路:
(x,0,0,0)||(0,x,0,0)——>必败态(0,0,0,0)。
异或等于零为必败态。
异或和等于零必然由异或和不等于零推出来的,异或和不等于零一定有某种方法可以推出异或和等于零。
例子:
1,4,2(A拿)异或和不等于零
——>1,3,2(B拿)异或和等于零
——>0,3,2(A拿)异或和不等于零
——>0,2,2(B拿)异或和等于零
——>0,1,2(A拿)异或和不等于零
——>0,1,1(B拿)异或和等于零
——>0,0,1(A拿)异或和不等于零
——>A胜
它总可以把一个异或和不为零的状态转化为异或和为零的状态,也总可以把一个异或和为零的状态转化为异或和不为零的状态。
code:
#include<iostream>
using namespace std;
void solve(){int n;cin>>n;int ans=0;for(int i=1;i<=n;i++){int x;cin>>x;ans^=x;}cout<<(ans ? "Yes":"No")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}
题目描述
栗酱特别喜欢玩石子游戏,就是两个人玩,有n堆石子,每堆有ai个,每次一个人可以轮流选择任意一堆,取走任意多的石子(但不能不取),谁先不能取谁输。
栗酱觉得这个游戏很有趣,知道有一天,小太阳告诉她,其实如果两个人足够聪明,游戏的结局一开始就已经注定。
栗酱是一个冰雪聪明的女孩子,她不相信,希望你演示给她看。
输入描述
多组数据,数据第一行T表示数据组数
每组数据第一行一个n,k表示一共有n堆石子,接下来你试图从第k堆开始取,从第二行开始,每隔一个空格一个
第i堆石子的数量ai.
n<=10 ^ 5,ai<=10 ^ 9
输出描述
输出“Yes"或“No"代表从该堆开始取是否可以必胜(如果足够聪明)。
输入
2
3 2
1 2 3
2 1
2 1
输出
No
Yes
说明
小太阳哥哥说,如果想赢,就试图把每堆石子数量的异或和变为0,最终便可以获得胜利,不相信自己证下。
解题思路
要改变一个数使其异或和为零,可以将一个数改为其余两个数的异或运算的答案。
分析No的数据:
3 2
1 2 3
要将1,2,3改变一个数使其异或和为零并且只可以改变第二个数,应该将其改为(1,3,3),但是本题只能拿走,不能增加,所以先手应该为必败态。
分析Yes的数据:
2 1
2 1
要将2,1改变一个数使其异或和为零并且只能改变第一个数,应将其改为(1,1),可以在第一堆中拿走一个所以先手必胜。
本题主要思路为现将除了第k位的数剩下的位数都进行 ^ 运算,然后需要地、第k位的数为剩下的数进行 ^ 运算的数,因为只有这样才可以让它异或和为零,如果这个数比原来的数大的话,不符合题意,则先手必败,如果这个数比原来的数小的话,符合题意,则先手必胜。
code:
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
void solve(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){if(i!=k) ans^=a[i];}cout<<(ans<a[k] ? "Yes":"No")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}
题目描述
有一些石子堆,第i堆有 ai个石子。你和算卦先生轮流从任一堆中任取若干颗石子(每次只能取自一堆,并且不能不取),取到最后一颗石子的人获胜。
算卦先生来问你,如果你先手,你是否有必胜策略?若是改动其中几个石子堆中石子的数量呢?
输入描述
第一行两个正整数 n,q,表示有 n 个石堆,q 次操作。
第二行 n 个整数,第i个数 ai表示第i个石堆初始有 ai个石子。
接下去 q 行,每行两个正整数 x,y,表示把第x堆石子的个数修改成 y。操作是累计的,也就是说,每次操作是在上一次操作结束后的状态上操作的。
输出描述
共q行,输出每次操作之后先手是否有必胜策略如果有,输出"Kan",否则输出"Li"
输入样例
5 4
6 7 3 4 5
1 6
2 1
2 4
5 5
输出样例
Kan
Kan
Li
Li
code:
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int n,q;
int main(){cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}int ans=0;for(int i=1;i<=n;i++){ans^=a[i];}for(int i=1;i<=q;i++){int x,y;cin>>x>>y;ans^=a[x];//将上次的第x位去掉,当一个数被异或运算两次,这个数会变成原来的数//一个数异或0不会改变这个数a[x]=y;ans^=a[x];cout<<(ans ? "Kan":"Li")<<'\n';}return 0;
}
题目描述
现在有两堆石子,两个人轮流从中取石子,且每个人每一次只能取1、3或9个石子,取到最后一个石子的人win.
假设先手后手都会选择最好的方式来取石子,请您判断先后手的输赢情况。
输入描述:
多组输入
每组一行,一行包括两个正整数n1和n2(1<=n1<=100,1<=n2<=100),代表了两堆石子的数目
输出描述:
如果先手能赢,输出"win";否则就输出"1ose"。
输入
1 1
1 2
输出
lose
win
code1:
#include<iostream>
#include<map>
using namespace std;
map<pair<int ,int>,bool>mp;
int f(int x,int y){if(mp.count({x,y})) return mp[{x,y}];bool res=false;if(x>=1)if(!f(x-1,y)) res=true;if(x>=3)if(!f(x-3,y)) res=true;if(x>=9)if(!f(x-9,y)) res=true;if(y>=1)if(!f(x,y-1)) res=true;if(y>=3)if(!f(x,y-3)) res=true;if(y>=9)if(!f(x,y-9)) res=true;return mp[{x,y}]=res;
}
int main(){int n,m;while(cin>>n>>m){cout<<(f(n,m) ? "win":"lose")<<'\n';}return 0;
}
解法思路2:
可以打表找规律
code2:
#include<iostream>
#include<map>
#include<iomanip>
using namespace std;
map<pair<int ,int>,bool>mp;
int f(int x,int y){if(mp.count({x,y})) return mp[{x,y}];bool res=false;if(x>=1)if(!f(x-1,y)) res=true;if(x>=3)if(!f(x-3,y)) res=true;if(x>=9)if(!f(x-9,y)) res=true;if(y>=1)if(!f(x,y-1)) res=true;if(y>=3)if(!f(x,y-3)) res=true;if(y>=9)if(!f(x,y-9)) res=true;return mp[{x,y}]=res;
}
void table(int n){cout<<' ';for(int i=1;i<=n;i++) cout<<setw(2)<<i<<' ';for(int i=1;i<=n;i++){cout<<setw(2)<<i<<' ';for(int j=1;j<=n;j++){cout<<setw(2)<<f(i,j)<<' ';}cout<<'\n';}
}
int main(){int n,m;table(20);return 0;
}
题目描述
大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考场浸润了十几载的当代人学生,Kikd和Cici更懂得考前的放松,所谓"张也有道"就是这个意思。这不,Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“叮五”?“还是“斗地丰”?
当然都不是!那多俗啊~
作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的:
1、 总共n张牌;
2、双方轮流抓牌;
3、每人每次抓牌的个数只能是2的幕次(即:1,2,4,8,16…)
4、抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?当然,打牌无论谁赢都问题不大,重要的是马上到来的CET-4能有好的状态。
Good luck inCET-4 everybody!
输入
输入数据包含多个测试用例,每个测试用例占一行,包含一个整数n(1<=n<=1000)
输出
如果Kiki能赢的话,请输出“Kiki”,否则请输出“Cici”,每个实例的输出占一行
输入数据
1
3
输出数据
Kiki
Cici
code1:
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
const int N=1010;
int dp[N];
int mex(set<int>st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x){if(dp[x]!=-1) return dp[x];set<int>st;for(int i=1;i<=x;i<<=1) st.insert(sg(x-i));return dp[x]=mex(st);
}
int main(){memset(dp,-1,sizeof(dp));int n;while(cin>>n){cout<<(sg(n) ? "Kiki":"Cici")<<'\n';}return 0;
}
解题思路2:
打表找规律,可以通过打表看出周期性,然后对其取模
code2:
#include<iostream>
#include<cstring>
#include<set>
#include<iomanip>
using namespace std;
const int N=1010;
int dp[N];
int mex(set<int>st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x){if(dp[x]!=-1) return dp[x];set<int>st;for(int i=1;i<=x;i<<=1) st.insert(sg(x-i));return dp[x]=mex(st);
}
int main(){memset(dp,-1,sizeof(dp));int n;cin>>n;for(int i=0;i<=n;i++) cout<<setw(2)<<i<<' ';cout<<'\n';for(int i=0;i<=n;i++) cout<<setw(2)<<sg(i)<<' ';return 0;
}
[SDOI2009] E&D
题目描述
小 E 与小 W 进行一项名为 E&D
游戏。
游戏的规则如下:桌子上有 2 n 2n 2n 堆石子,编号为 1 ∼ 2 n 1 \sim 2n 1∼2n。其中,为了方便起见,我们将第 2 k − 1 2k-1 2k−1 堆与第 2 k 2k 2k 堆( 1 ≤ k ≤ n 1 \le k \le n 1≤k≤n)视为同一组。第 i i i 堆的石子个数用一个正整数 S i S_i Si 表示。
一次分割操作指的是,从桌子上任取一堆石子,将其移走。然后分割它同一组的另一堆石子,从中取出若干个石子放在被移走的位置,组成新的一堆。操作完成后,所有堆的石子数必须保证大于 0 0 0。显然,被分割的一堆的石子数至少要为 2 2 2。两个人轮流进行分割操作。如果轮到某人进行操作时,所有堆的石子数均为 1 1 1,则此时没有石子可以操作,判此人输掉比赛。
小 E 进行第一次分割。他想知道,是否存在某种策略使得他一定能战胜小 W。因此,他求助于小 F,也就是你,请你告诉他是否存在必胜策略。例如,假设初始时桌子上有 4 4 4 堆石子,数量分别为 1 , 2 , 3 , 1 1,2,3,1 1,2,3,1。小 E 可以选择移走第 1 1 1 堆,然后将第 2 2 2 堆分割(只能分出 1 1 1 个石子)。接下来,小 W 只能选择移走第 4 4 4 堆,然后将第 3 3 3 堆分割为 1 1 1 和 2 2 2。最后轮到小 E,他只能移走后两堆中数量为 1 1 1 的一堆,将另一堆分割为 1 1 1 和 1 1 1。这样,轮到小 W 时,所有堆的数量均为 1 1 1,则他输掉了比赛。故小 E 存在必胜策略。
输入格式
本题有多组数据。
第一行一个整数 T T T,表示数据组数。
对于每组数据:
第一行一个整数 N N N,表示桌子上共有 N N N 堆石子,这里的 N N N 即为题目描述中的 2 n 2n 2n。
第二行 N N N 个整数 S 1 … N S_{1 \dots N} S1…N。
输出格式
对于每组数据,如果小 E 必胜,则一行一个字符串 YES
,否则一行一个字符串 NO
。
样例 #1
样例输入 #1
2
4
1 2 3 1
6
1 1 1 1 1 1
样例输出 #1
YES
NO
提示
对于 20 % 20\% 20% 的数据, N = 2 N=2 N=2。
对于另外 20 % 20\% 20% 的数据, N ≤ 4 N \le 4 N≤4, S i ≤ 50 S_i \le 50 Si≤50。
对于 100 % 100\% 100% 的数据, 1 ≤ T ≤ 20 1 \le T \le 20 1≤T≤20, 1 ≤ N ≤ 2 × 1 0 4 1 \le N \le 2 \times 10^4 1≤N≤2×104 且 N N N 为偶数, 1 ≤ S i ≤ 2 × 1 0 9 1 \le S_i \le 2 \times 10^9 1≤Si≤2×109。
解题思路:
本题由于数据太大,所以需要打表,sg函数代码直接求解为code1,code2为打表代码,code3为正解。
code1:
#include<iostream>
#include<map>
#include<set>
#include<vector>
using namespace std;
map<pair<int,int >,int>mp;
int mex(set<int>&st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x,int y){//设x>yif(x<y) return sg(y,x);if(y==0) return 0;if(mp.count({x,y})) return mp[{x,y}];set<int>st;//把x全部拿走,y给x i个for(int i=1;i<y;i++) st.insert(sg(i,y-i));//把y全部拿走,x给y i个for(int i=1;i<x;i++) st.insert(sg(x-i,i));return mp[{x,y}]=mex(st);
}
void solve(){int n;cin>>n;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];}int ans=0;for(int i=1;i<=n;i+=2){ans^=sg(s[i],s[i+1]);}cout<<(ans ? "YES" : "NO")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}
code2:
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
map<pair<int,int >,int>mp;
int mex(set<int>&st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x,int y){//设x>yif(x<y) return sg(y,x);if(y==0) return 0;if(mp.count({x,y})) return mp[{x,y}];set<int>st;//把x全部拿走,y给x i个for(int i=1;i<y;i++) st.insert(sg(i,y-i));//把y全部拿走,x给y i个for(int i=1;i<x;i++) st.insert(sg(x-i,i));return mp[{x,y}]=mex(st);
}
void solve(){int n;cin>>n;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];}int ans=0;for(int i=1;i<=n;i+=2){ans^=sg(s[i],s[i+1]);}cout<<(ans ? "YES" : "NO")<<'\n';
}
void table(int n){cout<<" ";for(int i=1;i<=n;i++) cout<<setw(2)<<i<<' ';cout<<'\n';for(int i=1;i<=n;i++){cout<<setw(2)<<i<<' ';for(int j=1;j<=n;j++){cout<<setw(2)<<sg(i,j)<<' ';}cout<<'\n';}
}
int main(){int n;cin>>n;table(n);return 0;
}
code3:
当x和y都是奇数时,就为零。
转移规律示意图:
规律:如果要找(20,5)则需要找到(10,ceil(5/2))
code3:
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
int sg(int x,int y){if(x<y) return sg(y,x);if((x&1)&&(y&1)) return 0;//x和y都为奇数//一般向上取整都是加分母减一if(x&1) return sg((x+1)/2,y/2)+1;//(x+1)/2代表向上取整,奇数加1是偶数所以可以这样向上取整,整体加一表示状态加1if(y&1) return sg(x/2,(y+1)/2)+1;return sg(x/2,y/2)+1;
}
void solve(){int n;cin>>n;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];}int ans=0;for(int i=1;i<=n;i+=2){ans^=sg(s[i],s[i+1]);}cout<<(ans ? "YES" : "NO")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}
[SDOI2011] 黑白棋
题目描述
小 A 和小 B 又想到了一个新的游戏。
这个游戏是在一个 1 × n 1 \times n 1×n 的棋盘上进行的,棋盘上有 k k k 个棋子,一半是黑色,一半是白色。
最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同。
小 A 可以移动白色棋子,小 B 可以移动黑色的棋子,其中白色不能往左,黑色不能往右。他们每次操作可以移动 1 1 1 到 d d d 个棋子。
每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。
小 A 和小 B 轮流操作,现在小 A 先移动,有多少种初始棋子的布局会使他胜利呢?
输入格式
输入三个数 n , k , d n,k,d n,k,d。
输出格式
输出小 A 胜利的方案总数。答案对 1 0 9 + 7 10^9+7 109+7 取模。
样例 #1
样例输入 #1
10 4 2
样例输出 #1
182
提示
- 对于 30 % 30\% 30% 的数据,有 k = 2 k=2 k=2。
- 对于 100 % 100\% 100% 的数据,有 1 ≤ d ≤ k ≤ n ≤ 1 0 4 1 \leq d \leq k \leq n \leq 10^4 1≤d≤k≤n≤104, k k k 为偶数, k ≤ 100 k \leq 100 k≤100。
题解
code:
#include<iostream>
#define int long long
using namespace std;
const int N=1e4+9,p=1e9+7;
int dp[25][N];//用于动态规划的数组
int fac[N];//存储阶乘的数组
int modpow(int a,int b){//快速幂计算(a^b%p)int res=1;while(b){if(b&1) res=res*a%p;a=a*a%p,b>>=1;}return res;
}
int inv(int x){//乘法逆元(x在模p下的逆元)return modpow(x,p-2);
}
int C(int n,int m){//计算组合数 C(n,m)if(n<m||n<0||m<0) return 0;return fac[n]*inv(fac[n-m]*fac[m]%p)%p;
}
int mo(int x){//确保结果为非负数return (x%p+p)%p;
}
signed main(){int n,k,d;cin>>n>>k>>d;fac[0]=1;for(int i=1;i<=n;i++){fac[i]=fac[i-1]*i%p;//存储0~n的阶乘}//先处理dp[0]for(int i=0;i<=k/2;i+=d+1) dp[0][i]=C(k/2,i);for(int i=1;i<=20;i++){for(int j=0;j<=n-k;j++){for(int l=0;l<=k/2;l+=d+1){//在第i位放置L个1if(j-(1ll<<i)*l>=0) dp[i][j]+=dp[i-1][j-(1ll<<i)*l]*C(k/2,l)%p;dp[i][j]%=p;}}}int ans=0;for(int i=0;i<=n-k;i++){//还剩下n-i-k个空位,放入(k/2)+1个间隙ans=(ans+dp[20][i]*C(n-i-k/2,k/2)%p)%p;}cout<<mo(C(n,k)-ans)<<'\n';return 0;
}
sg函数
sg()=0是必败态,sg()!=0时必胜态
sg(x)=n表示x点可以到达sg(y)=1,2,3…n-1的点(类似一个Nim游戏中的一堆石子)
Nim- K:
必败态:把石头个数进行二进制分解,对于每一位上的1的个数%(k+1)都为零
必胜态:其余情况
模型
Bash模型
当有n个数,每次减少[1,m],当n%(m+1)!=0时,前者为必胜态,否则为必败态。
Nim-1模型
在n堆石子中,每次任取一堆,取走若干个。在每次都取最优的情况下,初始状态为异或和不等于零,总有将此状态转化为异或和等于零的状态,最后可以得出先手必胜。
Nim-k模型
在n堆石子中,每次任选至多k堆,取走若干个。把所有数字(每堆上的石头个数)转化成二进制后,求每一位上1的个数,如果每一位都满足1的个数%(k+1)==0,那么就是必败态。