题目类型 博弈题
题目意思
给出 n 堆石子 (1 <= n <=1e5) 每堆石子有 Mi 种, 第1种有 Xi 个, 第2种有 Xi+1个, 依次类推 (1 <= Xi, Mi <=1e16)
两个人轮流从 n 堆石子中取石子, 每一次可以从 n 堆石子中其中一堆取其中一种的一部分(最少取这种石子的1个,最多可以全部取完) 不能取石子的输 假设两个人以最优方式来取 问最终赢的是谁
解题方法
基本模型是 Nim 游戏 传送门 -> 博弈论的一点资料,关于NIM和SG函数
最暴力的方法 就是把所有种类的石子数量 异或起来 看是0还是非0 但是显然会超时
可以这样考虑......
阅读全文