自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:38:30，当前版本为作者最后更新于2022-06-13 12:37:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

考虑计算 SG 函数。

根据题目描述，$i$ 的所有可能的后继状态为 $(j,i-c-j)$，$(j,i-z-j)$，$(j,i-n-j)$。故

$$\operatorname{SG}(i)=\operatorname{mex}\left\{\bigcup_{j}\{\operatorname{SG}(j)\oplus\operatorname{SG}(i-c-j),\operatorname{SG}(j)\oplus\operatorname{SG}(i-z-j),\operatorname{SG}(j)\oplus\operatorname{SG}(i-n-j)\}\right\}. $$

$O(n^2)$ 递推即可。

Code:

#include<cstdio>
#define rg register
int c,z,n,m,p,sg[1003],v[1073];int main(){
	scanf(" %d %d %d",&c,&z,&n);
	for(rg int i=1;i<=1e3;++i){
		for(rg int j=0;j<=1024;++j)v[j]=0;
		for(rg int j=0;j<=i-c;++j)
			v[sg[j]^sg[i-c-j]]=1;
		for(rg int j=0;j<=i-z;++j)
			v[sg[j]^sg[i-z-j]]=1;
		for(rg int j=0;j<=i-n;++j)
			v[sg[j]^sg[i-n-j]]=1;
		for(sg[i]=0;v[sg[i]];++sg[i]);
	}scanf(" %d",&m);while(m--){
		scanf(" %d",&p);printf("%d\n",\
		(sg[p])?1:2);}return 0;
}