一道ACM的题，请教各位？

8是不能赢的吧？
是不是这样？
2 no
3 no
5 no
8 no
是no的序列满足这样的a[n]=a[n-1]+a[n-2];
可是我不知道怎么证明啊？
请教！
----------------解决方案--------------------------------------------------------

重新推了一下,的确,8不能赢,7可以必胜
应该是这样
1 No
2 No
3 No
4 Yes
5 No
6 Yes
7 Yes
8 No
9 No

----------------解决方案--------------------------------------------------------

那我说的对吧？怎么证明呢？

----------------解决方案--------------------------------------------------------

题目不太理解

请问 必胜 是不是第一次随便取什么都是赢的意思啊 ？？？

----------------解决方案--------------------------------------------------------

想了好几天了，还没有解决！

----------------解决方案--------------------------------------------------------

从结果向前推就行了

----------------解决方案--------------------------------------------------------
不行吧？结果很多啊，我推出一个公式，不知道对不对？
----------------解决方案--------------------------------------------------------

当然不是了，我的理解是无论 Tom 取多少个，Jack都能赢

----------------解决方案--------------------------------------------------------
有时候做题是看灵感的，包括对数字的敏感，这题就是这样（至少我是这样做出来的）

我来分析一下，首先，这是一道博弈问题，看上去像一种Combinatorial Game
参考一下《Game Theory》--Thomas S. Ferguson
What is a Combinatorial Game? We now define the notion of a combinatorial
game more precisely. It is a game that satisfies the following conditions.
(1) There are two players.
(2) There is a set, usually finite, of possible positions of the game.
(3) The rules of the game specify for both players and each position which moves to
other positions are legal moves. If the rules make no distinction between the players, that
is if both players have the same options of moving from each position, the game is called
impartial; otherwise, the game is called partizan.
(4) The players alternate moving.
(5) The game ends when a position is reached from which no moves are possible for
the player whose turn it is to move. Under the normal play rule, the last player to move
wins. Under the mis`ere play rule the last player to move loses.
If the game never ends, it is declared a draw. However, we shall nearly always add
the following condition, called the Ending Condition. This eliminates the possibility of
a draw.
(6) The game ends in a finite number of moves no matter how it is played.
我们可以考虑动态规划求解这个问题，但是砝码的个数不足以刻画整个问题，因此我们需要加上一个参数，就是最大可以取走的砝码个数。
这样就需要一个二维的数组来存储。我们看到n的规模(1,100000)不允许我们使用n^2级的空间，先写一下状态转移方程看有没有办法节省。
dp[n][k]中n表示当前砝码的个数，用k表示当前可以最大取走的砝码个数。用dp[n][k]=1表示当前状态是一个先手必胜状态,dp[n][k]=0表示当前状态是一个先手必败状态。
dp[n][k]= !(dp[n-1][2*1]&&dp[n-2][2*2]&&...&&dp[n-k][2*k])
其中k>=n的状态显然是先手必胜状态，n<0的状态是没有意义的，这些我们暂时先不考虑。
总之根据这个状态转移方程是没办法节省空间。
然后我写了一个小规模的程序把2到100的结果打印出来，发觉是有规律的，2，3，5，8，13，21，...是NO，其他的是YES。如果你还看不出的话，我加上两个数你就看出来了，1,1,2,3,5,8,13,21,...
至此，我们当然可以大胆猜测～！◎＃￥，然后提交，AC，over。
----------------解决方案--------------------------------------------------------