博弈专题 sg函数子状态+链涂色

题目链接：https://vjudge.net/contest/299140#problem/J
题目大意：一个圆环N个珠子，每次每个人只能给连续的M个数珠子涂色，最后不能涂的就算输。

每次涂色后相当于把链分成没有涂色的两部分

根据sg定理：当前状态的SG函数等于各个子状态SG函数的异或和
所以枚举所有的子状态就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int sg[1010]={0};
int n, m;
int  get_sg(int len)
{
    if(len<m)//长度<m无法涂色
    {
        return 0;
    }
    if(sg[len]!=-1)
    {
        return sg[len];
    }
    bool vis[1010]={0};
    for(int i=0;i+m<=len;i++)
    {
        vis[get_sg(i)^get_sg(len-m-i)]=true;
    }
    for(int i=0;i<=len;i++)//mex
    {
        if(!vis[i])
        {
            return sg[len]=i;
        }
    }
}

int main()
{
    int T, CUT=0;
    scanf("%d",&T);
    while(T--)
    {
        CUT++;
        scanf("%d %d",&n,&m);
        printf("Case #%d: ",CUT);
        if(m==1)
        {
            if(n&1)
            {
                printf("aekdycoin\n");
            }
            else
            {
                printf("abcdxyzk\n");
            }
            continue;
        }
        memset(sg, -1, sizeof(sg));
        sg[0]=0;
        if(n>=m&&!get_sg(n-m))
        {
            printf("aekdycoin\n");
        }
        else
        {
            printf("abcdxyzk\n");
        }

    }

    return 0;
}