「HDU 1847」Good Luck in CET-4 Everybody

Description

一个公平组合游戏：

总共 $n$ 张牌；
双方轮流抓牌，两人都足够聪明；
每人每次抓牌的个数只能是 $2$ 的幂次（即：$1,2,4,8,16\ldots$）；
最后抓完牌的人为胜者。

$\rm Kiki$ 先手，$\rm Cici$ 后手，求最后谁能获胜。$(1 \leq n \leq 10^3)$

Source

[hdu]1847

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

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline bool read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) {
        if (c == EOF) return 0;
        f ^= c == '-';
    }
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
    return 1;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int main() {
    for (int n; read(n); ) {
        if (n % 3) puts("Kiki");
        else puts("Cici");
    }
    return 0;
}