自动搬运

查看原文

来自洛谷，原作者为

	Maniac丶坚果 **

搬运于2025-08-24 21:57:58，当前版本为作者最后更新于2018-02-17 08:32:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题属于一打表就太容易发现规律的题目。

首先上结论：

当a是奇数时，n为奇数则先手胜，反之则后手胜。

当a是偶数时，求n 对 a+1取模的值，这个值如果是奇数或等于a,则先手胜，否则后手胜。

可以很容易想到要把n转化为一个a进制的数。此时，两个操作转化成这样：

①选择非0的一位，使之-1

②选择0的一位，使之变为a-1,而对于这一位前面的所有位，如果也是0那么也变为a-1，直到遇到一个非0位使之-1.

所以，当a是奇数时，可以注意到无论原数是如何，选择了什么操作，每一次行动都会让原数二进制表达上每一位的和的奇偶性变化。而这一切的终点则是“1”的那个时候->先胜点，和为奇数。因此，初始局面的每一位的和如果是奇数那么先胜，否则后手胜。

而又不难发现，a为奇数时，a进制表达上的每一位$(1,a,a^2,a^3,a^4...)$也全都是奇数。所以奇数个奇数相加得到一定是得到奇数->因此只要判断n是否是奇数即可。

而a是偶数的时候则稍微复杂一些。

首先，想到a+1，你是需要发现它除了n < a且n为偶数的情况n = a+1应该算是一个显然的必败点了。在它以后的情况都是比较好分析的。

当局面变化到n < a+1的时候，由于只有-1或者-a的操作，可以显然得到如果n为偶数且$n \neq a$那么后手胜，否则先手胜。

由于$a^2 = (a-1)(a+1) + 1$,所以$a^2 \equiv1 (mod (a+1))$. 所以考虑$a^k mod (a+1)$，可以发现$2 | k$的时候$a^k mod (a+1)=1$,反之$=a$

所以，对于任意的一个偶数$k$和一个奇数$l$，一定有$a^k+a^l \equiv 0(mod(a+1))$

于是，如果是后手胜局，它可以容易在先手行动以后选择拿走$a^0$或$a^1$来使得 两人取掉数的和是a+1的倍数，除非数是形如$a^{2k}+l(l < a)$形式（有人取了$a^{2k}$以后无法再取$a$）。不过仔细思考可以把这种形态等价成$a^{2k} + l - (a^{2k}-1)$（一个整除a+1的数） $=l + 1$.，依然可以发现他是符合上面的规律的。

代码很简单：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20010;
bool a[maxn];
int n,m,p,q,mi[20],ans[20];
char ch[510];
inline int read()
{
    int x = 0, f = 1;
    char ch = 0;
    for (;!isdigit(ch);ch = getchar()) if (ch == '-') f = -1;
    for (;isdigit(ch);ch = getchar()) x = x *10 + ch - 48;
    return x * f;
}

int main()
{
    q = read();
    while (q--)
    {
        n = read(); scanf("%s",ch);
        int len = strlen(ch);
        if (n&1)
        {
            if (ch[len - 1]&1) puts("lsq Win"); else puts("wzt Win");
        }
        else
        {
            n++;
            int now = 0;
            for (int i = 0; i < len; ++i)
            {
                now = now * 10 + ch[i] - 48;
                now %= n;
            }
            if ((now) & 1 || now == n - 1) puts("lsq Win"); else puts("wzt Win");
        }
    }
}

话说比赛的时候，这个题我首先是早上起来看了一下然后就被拉去走亲戚了，但是整个过程中都没想到啥觉得很肯定的结论，然后回到家试着一打表看看就发现....