学习笔记 Nim

Nim

谁取到最后一个谁赢

定义 : 异或和为0 T态 异或和不为0 S态

定理1 对于任意一个S态 总能合理合法地使其转化为T态

这是可以证明的

还记得取火柴游戏吗 ? ? ?

\(x=a_1\ xor\ a_2\ xor\ a_3\ xor\ ......\ xor\ a_n>0\)

那么根据异或的意义 对于x的最高位 必定存在\(a_i\)与其最高位对应

那么$ a_{ii}=a_i\ xor\ x

所以我们仅需要从\(a_i\)当中取出\((a_i-a_ii)\)根火柴 S->T

定理2 对于任意一个T态 无论怎么取 都是转化为S态

反证法证明

\(x_1=a_1\ xor\ a_2\ xor\ a_3\ xor\ ......\ xor\ a_i\ xor\ ......\ xor\ a_n=0\)

\(x_2=a_1\ xor\ a_2\ xor\ a_3\ xor\ ......\ xor\ a_{ii}\ xor\ ......\ xor\ a_n=0\)

那么\(x_1\ xor\ x_2=a_1\ xor\ a_2\ xor\ a_3\ xor\ ......\ xor\ a_i\ xor\ ......\ xor\ a_n\ xor\ a_1\ xor\ a_2\ xor\ a_3\ xor\ ......\ xor\ a_{ii}\ xor\ ......a_n=0\)

也就是\(a_i\ xor\ a_{ii}=0\) 与已知矛盾 所以得证

那么 一开始为S态

先手可以先将S态转换为T态

然后就是后手 先手 后手 先手

由于每一次 后手面对的是T态 只可以将T态->S态

但是先手绝顶聪明 总是可以将S态->T态

那么 最后总会是后手面对全0的T状态 那么就是loser

同理一开始为T态。。。。。。

例题

【POJ1704】

【luogu1247】