HDOJ 2999 Stone Game, Why are you always there? 博弈 SG函數

[cpp]
//HDOJ 2999 Stone Game, Why are you always there?  博弈 SG函數 
/*
題意：有n個石子排成一行，每次只能取走連續的f個石子，f為給定的一個集合。
      問先手 勝負態
 
思路：局面不可能存在無法判斷的情況
      假設有4個石子 集合中只有一個數2
      則後繼狀態有｛0，2｝｛1，1｝，｛2，0｝
      因為｛0，2｝和｛2，0｝表示一樣的狀態 因此可以加一個剪枝
      
*/ 
 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
 
#define N 105 
#define M 1005 
 
int n,cnt; 
int op[N],sg[M]; 
 
int mex(int n){ 
    int i,j; 
    bool vis[1005]; 
    if(sg[n] != -1) 
        return sg[n]; 
    memset(vis,false,sizeof(vis)); 
    for(i = 1; i < cnt && op[i] <= n; ++i){ 
        for(j = 0; j+op[i] <= n && j < n/2+1 ; ++j){ 
            if(sg[j] == -1) 
                sg[j] = mex(j); 
            if(sg[n-j-op[i]] == -1) 
                sg[n-j-op[i]] = mex(n-j-op[i]); 
            vis[sg[j]^sg[n-j-op[i]]] = true; 
        } 
    } 
    for(i = 0; ; ++i) 
        if(vis[i]==false) 
            return i; 
} 
 
int cmp(const void *a,const void *b){ 
    return *(int *)a - *(int *)b; 
} 
 
int main(){ 
    int i,k,m; 
    while(scanf("%d",&n)!=EOF){ 
        for(i = 1; i <= n; ++i) 
            scanf("%d",&op[i]); 
        qsort(op+1,n,sizeof(op[0]),cmp); 
        cnt = 2; 
        for(i = 2; i <= n; ++i) 
            if(op[i] != op[i-1]) 
                op[cnt++] = op[i]; 
 
        memset(sg,-1,sizeof(sg)); 
        scanf("%d",&k); 
        while(k--){ 
            scanf("%d",&m); 
            if(sg[m] == -1) 
                sg[m] = mex(m); 
            puts(sg[m]?"1":"2");     
        } 
    } 
    return 0; 
}