卧薪尝胆,厚积薄发。
小乐乐学博弈
Date: Sat Dec 01 16:32:57 CST 2018 In Category: NoCategory

Description:

$x$ 堆石子,给出每堆石子的数量,每次从一堆里最多取 $k$ 个,问先后手谁赢。
$1\leqslant x\leqslant 10^6$

Solution:

首先从每堆里选最多 $k$ 个是一个巴什博弈,根据巴什博弈的结论一个人可以每次取 $k+1-$ 另一个人上一次取的个数,也就是说 $k+1$ 的倍数都没用,因为不会改变胜负情况,那就把每个数先都模 $k+1$ 最后剩的数都小于等于 $k$ ,也就是说可以随便取,那这就是一个尼姆游戏了,直接异或判断即可。

Code:


没写代码
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡