巴什博弈

简述

什么是巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取m个。最后取光者得胜。

分析

我们称先进行游戏的人为先手，另一个人为后手。

1、如果$n=m+1$，那么由于一次最多只能取$m$个，所以，无论先手拿走多少个，后手都能够一次拿走剩余的物品，后者取胜。
2、如果$n=(m+1)*r+s$，(r为任意自然数，$s≤m$),先手要拿走s个物品，如果后手拿走$k(k≤m)$个，那么先手再拿走$m+1-k$个，结果剩下$(m+1)*(r-1)$个，以后保持这样的取法，那么先取者肯定获胜。我们得到如下结论:要保持给对手留下$(m+1)$的倍数，就能最后获胜。

必胜态必败态

只要$n$不能整除$m+1$,那么必然是先手取胜，否则后手取胜。

变形

如果我们规定最后取光者输，那么又会如何呢？

$(n-1)$%$(m+1)==0$则后手胜利 先手会重新决定策略，所以不是简单的相反的。
例如$n=15，m=3$
后手 先手 剩余
   0      2    13
   1      3     9
   2      2     5
   3      1     1
   1      0     0
先手胜利 输的人最后必定只抓走一个，如果>1个，则必定会留一个给对手

例题

例题1.hdu 1846

题意：本游戏是一个二人游戏,有一堆石子一共有n个,两人轮流进行,每走一步可以取走1…m个石子,最先取光石子的一方为胜,如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
要求：Time Limit: 1000 MS , Memory Limit: 32768 K
思路：最基础的巴什博奕模版题，不多说。

#include<cstdio>

int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n%(m+1))
            printf("first\n");
        else
            printf("second\n");
    }

    return 0;
}

例题2.hdu 2147

题意：题目大意：就是有一个游戏，在一个$n*m$的矩阵中起始位置是$（1，m）$，走到终止位置$（n,1）$；游戏规则是只能向左，向下，左下方向走，先走到终点的为获胜者。
要求：Time Limit: 1000 MS , Memory Limit: 1000 K
思路：我们可以寻找必败态和必胜态，我们假设必败态是P，必胜态是N，那么当$n=8$、$m=9$时，必胜态必败态矩阵如下：
NNNNNNNNN
PNPNPNPNP
NNNNNNNNN
PNPNPNPNP
NNNNNNNNN
PNPNPNPNP
NNNNNNNNN
PNPNPNPNP
多试几组样例，我们可以很容易的发现，当$n$和$m$都为奇数的时候，按照题意，应输出“What a pity！”，否则输出“Wonderful！”。

#include<cstdio>
#include<cstring>

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)
            return 0;
        if(n%2==1&&m%2==1)
            printf("What a pity!\n");
        else
            printf("Wonderful!\n");
    }
    return 0;
}