hdu 1847 Good Luck in CET-4 Everybody! 组合游戏 找规律

题目链接

题意

有\(n\)张牌，两人依次摸牌，每次摸的张数只能是\(2\)的幂次，最后没牌可摸的人为负。问先手会赢还是会输？

思路

0	1	2	3	4	5	6	7	8	9	10	11	……

P	N	N	P	N	N	P	N	N	P	N	N	……

可归纳出：\(n\%3==0\)时为\(P\)，\(n\%3\neq 0\)时为\(N\).

证明：

因为\(2^k\%3\neq 0\)，

所以

1. \(n\%3==0\)只能由\((n-2^k)\%3\neq 0\)转移而来，而\((n-2^k)\%3\neq 0\)的状态全部为\(N\)，故\(n\%3==0\)的状态为\(P\).
2. \(n\%3\neq 0\)能由某个\((n-2^k)\%3==0\)转移而来，又因为\((n-2^k)\%3==0\)的状态为\(P\)，故\(n\%3\neq 0\)的状态为\(N\).

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {

    int n;

    while (scanf("%d", &n) != EOF) {

        n %= 3;

        if (n) puts("Kiki");

        else puts("Cici");

    }

    return 0;

}