AtCoder Beginner Contest 278

G - Generalized Subtraction Game

题意

• 给定 $n,l,r$，你需要和交互器博弈。
• 有一个长度为 $n$ 的区间，你和交互器轮流操作。
• 每次操作，操作的一方选择一个没有被染黑并且长度在 $l$ 和 $r$ 之间的区间，把它染黑。
• 无法操作的一方寄了，另一方获胜。

题解

直接求SG函数的话是 $O(n^3)$ 的，需要进行优化。

考虑模仿棋的策略，即选择中间的一段，将左右划分为两个长度相同的区间。此时先手必胜。但是，当 $l=r$ 且 $n-l\not\equiv 0\pmod 2$ 时策略会失效。此时，可以直接求SG函数，时间复杂度为 $O(n^2)$。