题解 P8369 【[POI2000]条纹】
VinstaG173
·
·
题解
考虑计算 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\}.
Code:
```cpp
#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;
}
```