基础知识

Nim游戏与SG函数

Nim游戏： 有 $n$ 堆石子，每堆有 $a_i$ 颗，每次可以拿走一堆中的任意颗，但是不能不拿。无法操作者失败。

可以证明，所有公平组合游戏都等价于一个单堆 Nim 游戏。¹又因为所有单堆 Nim 游戏互不相同，故我们可以给每个公平组合游戏分配一个正整数值，这个值就是 Sprague–Grundy 函数，简称 SG 函数。

题单链接 ZR 2026 Summer C 8.2

AGI

容易发现，若存在一些相等的两个数组成的数对，若 Menji 取走其中之一，Bot 可以取走另一来破坏两数异或和为 0。

所以关键在出现奇数次数的数。容易发现这样的数一定有偶数个。

当没有出现奇数次数的数，发现 Bot 一定可以照着 Menji 的取法取， Menji只能获得所有数对的其中一个数。此时当且仅当这些数异或和为 0 时 Menji 胜，否则 Bot 胜。

当有 2 个出现奇数次数的数，由于 Menji 先取，所以 Menji 可以挑选对他有利的那个数来试图构造 0 。

当有 4 及以上个，Bot 有足够的空间构造失利情况。此时 Bot必胜。

Generalized Subtraction Game

这道题用到了镜像博弈技巧。如果我们第一次操作将区间分为左右长度相等的两半，那么对面如何操作，我们直接复刻过来就行。此时我们取先手必胜。

以上策略需要满足 $n\equiv l\ (\text{mod }2)$ 或 $l<r$ 。若 $n\not \equiv l\ (\text{mod }2)$ 且 $l=r$ ，则需要根据 SG 函数选择先后手并且每次构造 SG 函数为 0 的情况。

1. 关于此处及以下的名词解释以及相关证明，参照OI-Wiki ↩︎