SSOJ2943取石子游戏1
822+
作者：crxis 发布：2022-03-11 分类：博弈论
题目大意：2个人取n个石子，每次至少取1颗，至多取m颗，无法操作则输，请问先手是否有必胜策略？
有一种有趣的游戏，玩法如下：
玩家： $2$ 人；
道具： $N$ 颗石子；
规则：
1、游戏双方轮流取石子；
2、每人每次取走若干颗石子（最少取 $1$ 颗，最多取 $K$ 颗）；
3、石子取光，则游戏结束；
4、最后取石子的一方为胜。
假如参与游戏的玩家都非常聪明，问最后谁会获胜？
【输入】
输入仅一行，两个整数 $N$ 和 $K$ 。
【输出】
输出仅一行，一个整数，若先手获胜输出 $1$，后手获胜输出 $2$。
【输入样例】
23 3
【输出样例】
1
【提示】
数据范围与提示：
对于全部数据， $1≤N≤10^5 ,1≤K≤N$。
解题思路
逐个试一下：0是必败，1~m是必胜，因为可以取1~m颗石子到0，让另一人无法操作。m+1是必败，因为他取完后，另一个人都是必胜状态。之后m个是必胜状态，因为他可以让另一人取的时候只剩下m+1个石子……
小结：能到必败的状态都是必胜状态，因为他可以当对手输；不能到必败状态则必败，因为下一次另一人的状态总是必胜。
程序实现
递推写法：
找到规律：
原来是这样用的 😉