题目：http://community.topcoder.com/stat?c=problem_statement&pm=13204&rd=15857

这道题目须要用到博弈论中的经典理论，Sprague–Grundy theorem，以下将相关理论做一个总结：

Impartial Game：公平游戏，两方除了谁先開始游戏外，其余都同样。

Nim：一类经典的Impartial Game，非常多游戏都能够等价于Nim。

Nimber（Grundy numbers）：能够理解为标识一个游戏状态的数。在游戏进行过程种，每一个状态都应一个唯一的Nimber。

Sprague-Grundy定理：对一个 Impartial Game 的状态，其等效游戏的 Nimber 数，就等于全部其后继状态 Nimber 数的 Mex 函数值。

Mex：对一个集合S，若G为S的补集，则 Mex{S} = min {G}。

依据 Sprague-Grundy定理，要求当前游戏状态的Nimber数，则须要求出其全部后继状态的Nimbers，然后对这些Nimbers取Mex值。并且当存在多个“子Impartial
Game”同一时候进行时，这一定理尤事实上用，对每一个“子游戏”状态的Nimber数进行异或操作，就是该状态的Nimber数。

代码例如以下：

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <iostream>

#include <sstream>

#include <iomanip>

#include <bitset>

#include <string>

#include <vector>

#include <stack>

#include <deque>

#include <queue>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <ctime>

#include <climits>

using namespace std;

#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)

typedef pair<int, int> pii;

typedef long long llong;

typedef pair<llong, llong> pll;

#define mkp make_pair

#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)

/*************** Program Begin **********************/

class GameOfSegments {

public:

    int winner(int N) {

	    int Nimbers[1001];

	    Nimbers[0] = Nimbers[1] = 0;

	    for (int i = 2; i <= N; i++) {

		    set <int> options;

		    for (int j = 0; j <= i - 2; j++) {

		    	options.insert(Nimbers[j] ^ Nimbers[i - j - 2]);

		    }

		    int r = 0;

		    while (options.count(r)) {

		    	++r;

		    }

		    Nimbers[i] = r;

	    }

	    return (Nimbers[N] > 0 ? 1 : 2);

    }

};

/************** Program End ************************/

參考：

http://www.cnblogs.com/fishball/archive/2013/01/19/2866311.html

http://www.cnblogs.com/hsqdboke/archive/2012/04/20/2459796.html

http://www.cnblogs.com/hsqdboke/archive/2012/04/21/2461034.html