利用这个性质：后续有必败态的当前一定是必胜态。

斐波那契博弈

有N颗石子，A先手，第一次他可以拿1～n-1个石子。后面拿的时候一定是1～2*上一次拿的石子数。拿到最后一颗石子的人是赢家。

打表：

bool dfs(int sum,int pre)
{
    if(sum==0)return false;//没有石子当前为必败态
    for(int i=1;i<=2*pre&&i<=sum;i++)
    {
        if(dfs(sum-i,i)==false)//后面有一个是必败态
            return true;//当前为必胜态
    }
    return false;
}
int main()
{
    for(int n=2;n<=30;n++)
    {
        int sign=0;
        for(int i=1;i<n&&sign==0;i++)
        {
            if(dfs(n-i,i)==false)//后手败
            {
                printf("%d:first %d\n",n,i);
                sign++;
            }
        }
        if(sign==0)printf("%d:second\n",n);
    }
    return 0;
}

Gym101775L

有1*n的方格，每个人可以写S或者O，如果从左到右出现了SOS，那么最后一个写S的人赢，问最后是谁赢或者平局。

打表：

这个存状态有点东西的，用char存的而且初始化成INF…的确比用orderedmap快多了…比初始化成0也快多了…

typedef unsigned long long ull;
#define INF 0x3f
int n;
int a[35];  //s:1,o:2
char mp[1000000000];
ull calc()
{
    ull temp=0;
    for(int i=1;i<=n;i++)
        temp=temp*3+1ll*a[i];
    return temp;
}
bool check()
{
    for(int i=1;i+2<=n;i++)
    {
        if(a[i]==1&&a[i+1]==2&&a[i+2]==1)
            return true;
    }
    return false;
}
void show()
{
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
    printf("\n");
}
int dfs(int step)
{
    ull sta=calc();
    if(mp[sta]^INF)return mp[sta];
    if(check())   //必败态
    {
        mp[sta]=-1;
        /*show();
        printf("%llu:-1\n",sta);*/
        return -1;
    }
    if(step==n+1)
    {
        /*show();
        printf("%llu:0\n",sta);*/
        return 0;  //平局
    }
    bool ex0=false;  //后续是否存在平局
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=0)continue;
        for(int j=1;j<=2;j++)
        {
            a[i]=j;
            int temp=dfs(step+1);
            if(temp==-1)    //后续存在必败态
            {
                mp[sta]=1;  //当前肯定是必胜态
                a[i]=0;
                /*show();
                printf("%llu:1\n",sta);*/
                return 1;
            }
            if(temp==0)ex0=true;
            a[i]=0;     //恢复标记
        }
    }
    if(ex0)
    {
        mp[sta]=0;
        /*show();
        /printf("%llu:0\n",sta);*/
        return 0;
    }
    mp[sta]=-1;
    /*show();
    printf("%llu:-1\n",sta);*/
    return -1;
}
int main()
{
    for(n=1;n<=30;n++)
    {
        memset(a,0,sizeof(a));
        memset(mp,INF,sizeof(mp));
        printf("%d:%d\n",n,dfs(1));
    }
    return 0;
}