HDOJ 3980 Paint Chain 博弈 SG函數

[cpp]
//HDOJ 3980 Paint Chain 博弈 SG函數 
 
/*
題意：有n個石子圍成一個環，每次從中取走m個連續的石子，無法取的輸
 
思路：第一步將取走之後環就變成了鏈，之後就可以用SG了
      所以特判第一步之後 先手變後手 後手變先手就可以了
*/ 
 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
 
#define N 1005 
 
int n,m; 
int sg[N]; 
 
int mex(int n){ 
    int i,res; 
    bool vis[N]; 
    if(sg[n] != -1) 
        return sg[n]; 
    memset(vis,false,sizeof(vis)); 
    for(i = 0; i+m <= n; ++i){ 
        if(sg[i] == -1) 
            sg[i] = mex(i); 
        if(sg[n-m-i] == -1) 
            sg[n-m-i] = mex(n-m-i); 
        vis[sg[i] ^ sg[n-m-i]] = true; 
    } 
    for(i = 0; ; ++i) 
        if(vis[i]==0) 
            return i; 
} 
int main(){ 
    int i,j; 
    int T,ca = 1; 
    scanf("%d",&T); 
    while(T--){ 
        scanf("%d %d",&n,&m); 
        printf("Case #%d: ",ca++); 
        if(m > n){ 
            puts("abcdxyzk"); 
            continue; 
        }  www.2cto.com
        else if(m == n){ 
            puts("aekdycoin"); 
            continue; 
        } 
        memset(sg,-1,sizeof(sg)); 
        n -= m; 
        puts(mex(n)?"abcdxyzk":"aekdycoin"); 
    } 
    return 0; 
}