【算法笔记】Bouton定理 2016年11月5日2016年11月5日 Qizy 2 Comments 概述 对于NIM游戏,相信大家都知道一个结论: 每一堆石子的数量给异或起来,若为0则先手必败,否则先手必胜 这个结论就是Bouton定理。 但对于这个定理,我一直没有找到简洁的证明 今日再一次翻看《白书》,终于觅得,于是记录于此 Bouton定理的结论 对于原版的NIM游戏 若每队石子的个数的NIM和为0,则先手必败 否则,先手必胜 Bouton定理的证明 参见《算法竞赛·入门经典·训练指南》P135 后记 为什么感觉这么鬼畜….. 最关键的证明部分是一个引用QAQ 唉,懒癌晚期,放弃治疗…..