博弈-翻硬币游戏

博弈-翻硬币游戏 翻硬币游戏一般的翻硬币游戏的规则是这样的N 枚硬币排成一排有的正面朝上有的反面朝上。我们从左开始对硬币按 1 到 N 编号。 第一游戏者根据某些约束翻硬币但他所翻动的硬币中最右边那个硬币的必须是从正面翻到反面。例如只能翻 3 个硬币的情况那么第三个硬币必须是从正面翻到反面。如果局面是正正反那就不能翻硬币了因为第三个是反的。 第二谁不能翻谁输。有这样的结论局面的 SG 值为局面中每个正面朝上的棋子单一存在时的 SG 值的异或和。即一个有 k 个硬币朝上朝上硬币位置分布在的翻硬币游戏中SG 值是等于 k 个独立的开始时只有一个硬币朝上的翻硬币游戏的 SG 值异或和。比如 THHTTH 这个游戏中2 号、3号、6 号位是朝上的它等价于 TH、TTH、TTTTTH 三个游戏和即sg=sg^sg^sg.我们的重点就可以放在单个硬币朝上时的SG值的求法。约束条件一每次只能翻一个硬币。一般规则中所翻硬币的最右边必须是从正面翻到反面因为这题是只能翻一个硬币那么这个硬币就是最右边的硬币所以每次操作是挑选一个正面的硬币翻成背面。对于任意一个正面的硬币SG 值为 1。有奇数个正面硬币局面的 SG 值==1先手必胜有偶数个正面硬币局面的 SG 值==0先手必败。约束条件二每次能翻转一个或两个硬币。(不用连续)每个硬币的 SG 值为它的编号初始编号为 0与 NIM 游戏是一样的。如果对于一个局面把正面硬币的 SG 值异或起来不等于 0既 a1^a2^a3^…^an==x,对于an 来说一定有 an'=an^x