$\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;
}