考虑计算 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;
}

$\operatorname{Description}$

给定一段长度为 $n$ 的线段。现有两人轮流进行操作，每次在线段中移除连续的一段，且移除线段的长度只能为 $c,z,n$ 中的任意一个。

现给出多条线段，问对于长度为 $len_i$ 的线段，先手是否有必胜策略。

$\operatorname{Solution}$

易发现该游戏符合 $ICG$ 的所有性质，于是考虑使用 $SG$ 函数计算。

我们设 $SG(i)$ 表示长度为 $i$ 的线段对于先手而言是否有必胜策略。

显然有 $SG(0)=0$。

对于一条长度为 $len$ 的线段而言，设对其进行一次操作取走的长度为 $w$，取走的那一段区间左区间长度为 $left$，那么当前长度为 $len$ 的线段就被我们分成了三部分：

• 被取走的那段长度为 $w$ 的线段，我们取走该部分之后该部分的状态变为 $SG(0)$。
• 被取走区间左边的区间，即长度为 $left$ 的一段线段，在我们进行操作之后其状态就是 $SG(left)$。
• 被取走区间右边的区间，即长度为 $len-w-left$ 的一段线段，我们进行操作之后其状态为 $SG(len-w-left)$。

因为被取走的区间 $SG$ 值变为 $0$，在异或时并不会对结果产生任何影响。

所以我们每进行一次操作，实际上就是将当前局面分成左右区间两个子局面。

递推 $O(n^2)$ 求 $SG$，然后 $O(1)$ 回答询问即可。

时间复杂度 $O(n^2)$。

$\operatorname{Code}$

#include<bits/stdc++.h>
#define M 2005
using namespace std;
int a[4],t,n,sg[M];
int main(){
    scanf("%d%d%d%d",&a[1],&a[2],&a[3],&t);
    for(int i=1;i<=1000;i++){
        set<int>s;
        for(int j=0;j<=i-a[1];j++) s.insert(sg[j]^sg[i-j-a[1]]);
        for(int j=0;j<=i-a[2];j++) s.insert(sg[j]^sg[i-j-a[2]]);
        for(int j=0;j<=i-a[3];j++) s.insert(sg[j]^sg[i-j-a[3]]);
        int fl=0;
        while(s.count(fl)) ++fl;
        sg[i]=fl;
    }
    while(t--){
        scanf("%d",&n);
        printf("%c\n",sg[n]?'1':'2');
    }
    return 0;
}