HDU 1846：Brave Game ← SG 函数 + 巴什博奕（Bash Game）
【题目来源】
http://acm.hdu.edu.cn/showproblem.php?pid=1846
【题目描述】
十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。
今天，大家选择上机考试，就是一种勇敢（brave）的选择；这个短学期，我们讲的是博弈（game）专题；所以，大家现在玩的也是“勇敢者的游戏”，这也是我命名这个题目的原因。
当然，除了“勇敢”，我还希望看到“诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~
各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
【输入格式】
输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。
【输出格式】
如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。
【输入样例】
2
23 2
4 3
【输出样例】
first
second
【数据范围】
C<=100，
1<=n,m<=1000
【算法分析】
● 巴什博弈（Bash game）是一种涉及 2 名玩家的双人博弈，属于公平组合游戏（ICG）的典型例子。 博弈中有一堆总数为 n 的物品，2 名玩家轮流从中拿取物品，每次至少拿 1 件，至多拿 m 件，不能不拿，最终将物品拿完者获胜。
（1）n≤m 时，由于一次最少拿一个，最多拿 m 个，甲可以一次拿完，先手赢。
（2）n=m+1 时，无论甲拿走多少个 （1~m 个），剩下的都多于 1 个且少于或等于 m 个，乙都能一次拿走剩余的石子，后手取胜。
● Bash 博弈胜负判定（每次取 1～m 个，取走最后一个石子的胜）
（1）如果 n%(m+1) == 0，即 n 是 m+1 的整数倍，那么不管甲拿多少（记作 k，其中 1≤k≤m），乙都拿 m+1-k 个，使剩下的永远是 m+1 的整数倍，直到最后的 m+1 个，所以后拿的乙一定赢（后手赢）。
（2）如果 n%(m+1) != 0，即 n 不是 m+1 的整数倍，还有余数 r，那么甲拿走 r 个，剩下的是 m+1 的倍数，这样就转移到了情况（1），相当于甲乙互换，结果是先拿的甲赢（先手赢）。
● 巴什博弈（Bash Game）SG 值完整推导
（1）游戏规则：有一堆 n 个石子，两人轮流取石子，每次可以取 1~m 颗，不能不取，取走最后一颗石子者获胜。
（2）定义：SG(x) 表示剩余石子数为 x 时的 SG 函数值。
（3）SG 函数定义：SG(x) = mex{ SG(y) | y 是 x 的一步后继状态 }。其中，mex(S) 表示集合 S 中最小的非负整数。
一步后继状态：从 x 拿走 k（1≤k≤m）颗石子，到达状态 x - k。
（4）边界条件
x=0：没有石子，是必败态（当前玩家无操作可做）。
没有后继状态，后继集合为空集 ∅。SG(0)=mex(∅)=0。
（5）计算小例子，找规律（设 m=3，每次可取 1, 2, 3 颗）
x=1：后继为 1-1=0，后继 SG 集合为 {SG(0)}={0}，则得 SG(1)=mex{0}=1 x=2：后继为 2-1=1，2-2=0，后继 SG 集合为 {SG(1),SG(0)}={1,0}，则得 SG(2)=mex{0,1}=2 x=3：后继为 3-1=2，3-2=1，3-3=0，后继 SG 集合为 {SG(2),SG(1),SG(0)}={2,1,0}，则得 SG(3)=mex{0,1,2}=3 x=4：后继为 4-1=3，4-2=2，4-3=1，后继 SG 集合为 {SG(3),SG(2),SG(1)}={3,2,1}，则得 SG(4)=mex{1,2,3}=0 x=5：后继为 5-1=4，5-2=3，5-3=2，后继 SG 集合为 {SG(4),SG(3),SG(2)}={0,3,2}。则得 SG(5)=mex{0,2,3}=1 x=6：后继为 6-1=5，6-2=4，6-3=3，后继 SG 集合为 {SG(5),SG(4),SG(3)}={1,0,3}。则得 SG(6)=mex{0,1,3}=2 x=7：后继为 7-1=6，7-2=5，7-3=4，后继 SG 集合为 {SG(6),SG(5),SG(4)}={2,1,0}。则得 SG(7)=mex{0,1,2}=3 x=8：后继为 8-1=7，8-2=6，8-3=5，后继 SG 集合为 {SG(7),SG(6),SG(5)}={3,2,1}。则得 SG(8)=mex{1,2,3}=0 观察规律 (m=3)：SG(0)=0，SG(1)=1，SG(2)=2，SG(3)=3，SG(4)=0，SG(5)=1，G(6)=2，SG(7)=3，SG(8)=0，…。 猜想一般式：SG(n)=n mod (m+1)。证明略。【算法代码一：SG函数写法】
注意：当n<10^4时，如下 SG 函数写法的代码是安全的。否则，极易触发 Segmentation Fault 及 TLE。
#include <iostream> #include <cstring> using namespace std; const int N=1e3+5; int sg[N]; bool st[N]; void SG(int n,int m) { sg[0]=0; for(int i=1; i<=n; i++) { memset(st,0,sizeof st); for(int j=1; j<=m && j<=i; j++) { st[sg[i-j]]=true; } int mex=0; while(st[mex]) mex++; sg[i]=mex; } } int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; SG(n,m); if(sg[n]!=0) cout<<"first\n"; else cout<<"second\n"; } return 0; } /* in: 2 23 2 4 3 out: first second */【算法代码二：非SG函数写法】
#include <iostream> using namespace std; int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; if(n%(m+1)==0) { cout<<"second\n"; } else cout<<"first\n"; } return 0; } /* in: 2 23 2 4 3 out: first second */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/163572528
https://blog.csdn.net/hnjzsyjyj/article/details/158802453