nim游戏: n堆石子, 两个人轮流操作, 每次任选一非空堆拿走至少一颗石子, 若无法操作则失败.
结论: n堆石子个数异或和为0则先手必败, 否则必胜.
证明: 假设初始异或和为0, 先手选择一堆$x$, 拿完剩余$y$, 剩余堆的异或和变为$xwedge y$, 那么一定可以找到一堆$a$, $a$二进制中最高位等于$xwedge y$的最高位, 即$a>awedge xwedge y$, 那么就可以将$a$变为$awedge xwedge y$, 则异或和重变为0, 所以先手必败. 若初始异或和为$t>0$, 则可按上述后手操作将异或和转为0, 从而必胜.
阶梯nim: n堆石子, 两个人轮流操作, 每次任选第$i$堆拿走至少一颗石子放在第$i-1$堆, 若选第$1$堆则直接拿走.
结论: 阶梯nim等价于奇数堆nim.
证明: 假设初始奇数堆异或和为0, 假设先手选第$i$堆移动$x$, 若$i$为偶数, 则后手将$i-1$移走$x$即可使异或和保持为0. 若$i$为奇数, 后手采用普通nim的策略即可使奇数堆异或为0. 所以先手必败. 若初始异或和为$t>0$, 先手用普通nim的策略将奇数堆异或和转为0即可必胜.
CF 812E Sagheer and Apple Tree
大意: 给定树, 每个节点有苹果, 所有叶子深度奇偶性相同, 两人轮流操作, 任选一节点选至少一颗苹果, 若不为叶子, 则将苹果放在任意儿子节点上, 若为叶子则吃掉. 不能操作则失败, 后手可以任选两个节点交换苹果数, 必须交换恰好一次, 求后手必胜可以交换的方案数.
根据阶梯nim的结论, 只要保证与叶子同奇偶的层数异或和为0, 则后手必胜.