A simple stone game(HDU-2486)

题面

After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier.

The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k * m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.

输入

The first line contains a integer t, indicating that there are t test cases following.(t<=20). Each test case is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

输出

For each test case, output one line starting with “Case N: ”, N is the case number. And then, if the first player can ensure a winning, print the minimum number of stones he should take in his first turn. Otherwise, print “lose”. Please note that there is a blank following the colon.

样例输入

15
216 1
311 1
432 2
534 2
619 3

样例输出

1Case 1: lose
2Case 2: 1
3Case 3: 3
4Case 4: lose
5Case 5: 4

提示

When k = 1, the first player will definitely lose if the initial amount of stones is in the set {2, 4, 8, 16, 32, …}. Let’s call this kind of set “first-player-lose set”.

When k = 2, the first-player-lose set is {2, 3, 5, 8, 13, 21, 34, 57 …} , which happens to be the Fibonacci sequence starting from 2.

思路

K倍动态减法博弈，参照斐波那契博弈和齐肯多夫定理的证明过程，将 $ f_{i} = f_{i-1} + f_{i-2} $ 替换为 $ f_{i} = f_{i-1} + f_{k} \mid_{ K \times f_{k-1} \lt f_{i-1} \le K \times f_{k}} $ ，也就是将齐肯多夫定理表述中的 若干不连续的项 替换为 若干两两之比大于K项。预处理出类似斐波那契博弈中的斐波那契序列，面对局势为序列项的，先手必败。

注意时间复杂度为 $ O(Tlog_{\frac{k+1}{k}}N) \approx 2 \times 10^{8} $，卡常。

详细参考《从“k倍动态减法游戏”出发探究一类组合游戏问题》、[POJ3922]Now解题报告。

同POJ-3922 A simple stone game。

代码

 1using namespace std;
 2int f[1000005] = {1};
 3
 4int main()
 5{
 6    int T; scanf("%d", &T);
 7    for(int cs=1; cs<=T; cs++)
 8    {
 9        int n, k;
10        scanf("%d %d", &n, &k);
11
12        int i=1, j=0;
13        for(; f[i] <= n; i++){
14            for(; 1LL * k * f[j] < f[i]; j++);
15            f[i+1] = f[i] + f[j];
16        }
17        i--;
18
19        printf("Case %d: ", cs);
20        if(f[i] == n){
21            printf("lose\n");
22        }else{
23            while(n != f[i]){
24                for(n-=f[i]; n<f[i]; i--);
25            }
26            printf("%d\n", n);
27        }
28    }
29    return 0;
30}