POJ.3537 Crosses and Crosses

1.Problem
http://poj.org/problem?id=3537

2.Idea
Calc grundy

3.Source

 int dp[2001];  
 int grundy(int n) {  
      if (n <= 0) return 0;  
      if (~dp[n]) return dp[n];  
      vector<int> vis(1 << 11);  
      for (int i = 1; i <= n; ++i) {  
           vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;  
      }  
      for (int i = 0; ; ++i) {  
           if (!vis[i]) return dp[n] = i;  
      }  
 }  
 void solve()  
 {  
      std::memset(dp, 0xff, sizeof(dp));  
      int n;  
      cin >> n;  
      cout << (grundy(n) ? 1 : 2) << endl;  
 }