[POJ2234]Matches Game

Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.

The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.

For each test case, output "Yes" in a single line, if the player who play first will win, otherwise output "No".

2 45 45
3 3 6 9

No
Yes

POJ Monthly,readchild

　　Nim游戏的经典模型。

　　随机博弈指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：1)每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子；2)如果谁取到最后一枚石子就胜。也就是尼姆博弈（Nimm Game）。必败局面：也叫奇异局势。无论做出何出操作，最终结果都是输的局面。必败局面经过2次操作后，可以达到另一个必败局面。必胜局面：经过1次操作后可以达到必败局面。即当前局面不是必败局面就是必胜局面，而必胜局面可以一步转变成必败局面。