尼姆博弈:
一:给定n堆石子,每次可以从一堆中取任意数量个,最后一个取完的获胜。
二:给定n堆石子,每次可以从一堆中取最多k个,最后一个取完的获胜。
三:给定n堆石子,每次可以选最多k堆,每堆可以取任意数量个。
Solution:
一:这是最经典的一种尼姆博弈,先手必胜态为所有堆石子数异或后答案不为0.否则为必败态。
二: 对每堆的石子数模上(k + 1),就变成了经典的尼姆博弈类型。
三:这个问题又被称为nimk博弈,我们把每堆石头都表示成二进制,从每个二进制位去考虑。
统计每个二进制位上1的个数,如果满足每个二进制位上1的个数都可以 % (k + 1) = 0.那么先手必败。
反之,先手必胜。