自动搬运

查看原文

来自洛谷，原作者为

	KesdiaelKen **

搬运于2025-08-24 22:14:39，当前版本为作者最后更新于2019-12-19 15:48:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题为博弈论+数论题目，只需转化一下模型即可。

生成函数只是个随机函数，按题意生成数据。其实是因为直接给数据文件太大无法上传

下面分数据编号进行讲评。

$1$

$m\le5$，用$bool$数组$f[i][j][k][s][t]$表示某个状态下为必胜或必败（指的是面对当前局面人的胜负状态）。$f[k][k][k][k][k]$为末状态，必败。每个状态可以有若干个下接状态（进行一次设计后可以形成的不违规状态）。容易想到，如果所有下接状态均为必胜，则此状态必败；否则必胜。记忆化搜索即可。

$2$

用$k$减去每个初始示数，题意就可以理解为在任意一个位置上减$1$，不够减则借位。每个数从$0$到$k$。这不就是$k+1$进制的减法吗？于是，题意转化为：给出$n$个数，每次减去$(k+1)^i$，$i$为任意自然数，不能减到小于$0$，轮流操作，问谁会面对全$0$的局面。则考虑每个数的胜负情况（记为$f[i]$）。

对于此点$n=1$，只需考虑一个数的$f[i]$。由于$2$点$m,k$范围较大，不能像$1$那样枚举下接状态。考虑$f[i]$是否具有规律。发现对于$k$的奇偶不同，规律不同：下面分情况证明：

对于$k$为偶数，当$2|i$时$f[i]=false$（败），否则为$true$（胜）。证明：数学归纳法。当$i=0,1$时成立。当$i>1$，由于$2|k$，$2\not|(k+1)^i$，$i-(k+1)^i$与$i$不同奇偶，则若$i$为偶，所有$i-(k+1)^i$为奇，$f[i-(k+1)^i]=true$，则$f[i]=false$。$i$为奇同理。

对于$k$为奇数，当$i>k+1$，$f[i]\equiv f[i\mod (k+2)]$；当$i\le k+1$，$f[i]=true$时$(2\not|i )or(i=k+1)$，$f[i]=false$时$(2|i)and(i\not=k+1)$。证明：数学归纳法。当$i=0\space to\space k+1$时易知成立。当$i>k+1$时，$(k+1)^i=1\space or\space -1(\mod k+2)$，则类似$k$为偶数时进行归纳。

$k$为偶数的时候也可以转化为$f[i]$以$k+2$为循环的规律。

规律得出，则可做。

$3$

存不下转换后的数。但考虑到最后的数要对$k+2$取模，可以在读入的时候同时取模。因为是$k+1$进制，对于奇数位，模$k+2$的值为$-1$乘此位上的数；对于偶数位，模$k+2$的值为$1$乘上此位上的数。

$6-8$

有多个数，$k$为偶数。先求出每个初始数的$f$。由以上证明可看到$k$为偶数时，赢状态的所有下接状态都为输状态，而输状态的所有下接状态都为赢状态。末状态所有数都为$0$，有偶数个赢状态。对于所有数，一次射击只能将一个数的$f$变为相反的一个状态。因此对于一个人，他面对的所有数中赢状态总数一定。所以，若先手面对奇数个赢状态则必赢，偶数个则必输。

$5$

每个数都小于等于$k$，即不可能取到$k$为奇数的特殊状态$i\equiv k+1(\mod k+2)$，等同于$k$为偶数的状态，即赢状态只接输状态，输状态只接赢状态。做法同上。

$4$

只有两个数，可以进行特殊讨论解决。

$9-17$

$f[i]$只保存赢或输不能为解决复杂的博弈信息提供足够有效信息。需要使用$sg$函数解决（不懂可看sg函数详解或自行查找资料）。令$f[i]$表示数$i$的$sg$函数值。同上用数学归纳法可证明：$k$为偶数时，将$true$转为$1$，$false$转为$0$即可；$k$为奇数时，对于$i\not\equiv k+1(\mod k+2)$，同上转换，否则$f[i]=2$。之后将每个数的$sg$函数值异或，异或值为$0$时必败，否则必胜。

事实上这个结论不用$sg$函数也可以推的出来。

标程：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;
unsigned long long k,a,b,c,sg,x,lc;
inline unsigned long long generate(unsigned long long&a,unsigned long long&b,unsigned long long&c,unsigned long long&k)
{ 
	a<<=19;a+=b+c;
	a<<=26;a^=c+=a+81;b--;
	a<<=7;a>>=(b^c^1145)&14;
	c*=a;a|=b+=c;a^=b&c;
	return a%(k+1);
}
int main()
{
	int n,m,t;scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%d%d%lld%lld%lld",&k,&n,&m,&a,&b,&c);
		x=0;
		for(int i=1;i<=n;i++,x^=sg)
		{
			sg=0;
			for(int j=1;j<=m;j++)
			{
				lc=generate(a,b,c,k);
				sg=(sg+((j&1)?(k-lc):(lc+2)))%(k+2);
			}
			if((k&1)&&sg==k+1)sg=2;
			else sg&=1;
		}
		if(x)printf("YES\n");else printf("NO\n");
	}
	return 0;
}