Description
一个公平组合游戏:
- 总共 $n$ 张牌;
- 双方轮流抓牌,两人都足够聪明;
- 每人每次抓牌的个数只能是 $2$ 的幂次(即:$1,2,4,8,16\ldots$);
- 最后抓完牌的人为胜者。
$\rm Kiki$ 先手,$\rm Cici$ 后手,求最后谁能获胜。$(1 \leq n \leq 10^3)$
Source
Solution
$\rm SG$ 函数经典例题。
我们把这个游戏放到一个 DAG 上。
最终取完牌的状态是 $0$,$0$ 没有后继状态,所以 $sg_0 = {\rm mex}(\varnothing ) = 0$,且这个点是必败点。
剩 $1$ 张牌的时候只能取走 $1$ 张,即 $1$ 的后继状态只有 $0$,所以
$sg_1 = {\rm mex}(\{sg_0\}) = {\rm mex}(\{0\})=1$ 。
剩 $2$ 张牌的时候能取走 $1$ 张或 $2$ 张,即 $2$ 的后继状态有 $1$ 和 $0$,所以
$sg_2 = {\rm mex}(\{sg_0,sg_1\}) = {\rm mex}(\{0,1\})=2$ 。
剩 $3$ 张牌的时候也能取走 $1$ 张或 $2$ 张,即 $3$ 的后继状态有 $2$ 和 $1$,所以
$sg_3 = {\rm mex}(\{sg_1,sg_2\}) = {\rm mex}(\{1,2\})=0$ 。
剩 $4$ 张牌的时候能取走 $1$ 张,$2$ 张或 $4$ 张,即 $4$ 的后继状态有 $3,2$ 和 $0$,所以
$sg_4 = {\rm mex}(\{sg_0,sg_2,sg_3\}) = {\rm mex}(\{0,2\})=1$ 。
同理我们能得到 $sg_5 = 2,sg_6 = 0,sg_7 = 1$ 。
$sg_0$ | $sg_1$ | $sg_2$ | $sg_3$ | $sg_4$ | $sg_5$ | $sg_6$ | $sg_7$ |
---|---|---|---|---|---|---|---|
$0$ | $1$ | $2$ | $0$ | $1$ | $2$ | $0$ | $1$ |
综上所述我们可以列出一个表格,很容易发现规律:$sg_n = n \bmod 3$ 。
所以当 $n$ 能被 $3$ 整除时,它的 $\rm SG$ 函数值为 $0$,即先手必败。
反之则先手必胜。
Code
1 |
|