结论:当 nnn 是奇数的时候 dd 必胜,反之 bb 必胜。下面我们来准备证明一下,但我们的证明围绕了一个好东西:
如果一种游戏的最终局面(某一方输)满足某一性质,并且游戏中所有满足该性质的局面所能创造出的新局面都不满足该性质,同时所有不满足该性质的局面一定可以产生出至少一个满足该性质的局面,那么我们就可以根据最初局面是否满足这个性质来判断先手是否必胜。
证明:
当 n=1n=1n=1 的时候玩家就输了,最终局面满足结论性质。
如果当前局面是一个奇数,那么下一次一定可以选择一个偶数。
如果是偶数,那么一定可以分割成两个奇数,产生奇数局面。
代码