题解 Topcoder SRM789 FollowingNim

题目链接

题意

给定 \(n\) 堆石子 \(a_1,a_2,\cdots,a_n\) 和一个集合 \(S\)，两名玩家轮流行动，每次可以在某堆石子中取走 \(x\) 个（不能不取）。特殊地，如果 \(x \in S\)，那么下一次行动的玩家只能在同一堆石子中取。不能行动者负。

注意如果某名玩家选择将某堆大小为 \(x\) 的石子取空并且 \(x \in S\)，那么下一名玩家告负，因为它被迫尝试对一个空堆进行操作。

\(1 \leq n,|S| \leq 50,1 \leq a_i \leq 100,\ \forall x \in S, 1 \leq x \leq 100\)

题解

非常有意思的一道题。

考虑一个博弈论经典策略，即将对手的必胜策略变成自己的。

如果先手取了某个 \(x \in S\)，此时如果后手的必胜策略是取 \(y \notin S\)，那么先手可以直接取 \(x+y\)（\(x+y\) 是否属于 \(S\) 并不重要，如果是只会让后手更难赢），把后手的必胜策略变成自己的，因此后手不会这么做。

因此，如果先手取了 \(x \in S\)，那么后手也一定取 \(y \in S\)。如果存在某个堆，使得先后手轮流取在 \(S\) 中的元素，先手胜利，那么先手就直接胜利。我们定义这个局面为好的。

否则，先手不能取 \(x \in S\)，并且要保证取了之后的局面仍然不能是好的。为了方便起见，我们令后手可以随意行动，如果此时后手存在必胜策略，那么根据上面的结论，后手取 \(y \in S\) 时也必然存在必胜策略。如果后手可以随意行动，那么这个游戏等价于若干个相同游戏的组合，求出 SG 函数后计算异或即可。