POJ-2234:Matches Game

시간 제한:
1000ms 
메모리 제한:
65536kB
묘사
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

(1) 이것은 바둑론 Nim Game의 제목이다. 우리는 간단한 상황부터 분석하고 점차적으로 깊이 들어가자.
(1) 한 무더기, 먼저 이기기 (2) 두 무더기, 모두 두 개의 성냥, 뒷손이 이기기 (한 무더기를 다 뽑으면 된다) 두 무더기, 모두 세 개의 성냥, 먼저 이기기 (1+2 구조, 두 개의 한 무더기에서 하나를 뽑아 이전의 상황으로 전환) 두 무더기, 한 무더기 2개, 다른 한 무더기 2개, 뒷손이 이기기 (한 무더기를 뽑거나 하나를 빼면 반드시 진다) 두 무더기, 한 무더기 1개, 다른 무더기 3개,선수승 (1+3 구조, 3개의 한 무더기에서 2개를 취하고 2개로 바뀌는 상황)...두 무더기, 성냥 더미 수가 같고, 뒷손이 두 무더기를 이기고, 성냥 더미 수가 같지 않다.2.2.1형 선수승 (항상 두 무더기로 바뀔 수 있기 때문에) 세 무더기, 모두 6개의 성냥, 2.2.2형 선수승 세 무더기, 모두 6개의 성냥, 1.4형 선수승 세 무더기, 모두 6개의 성냥, 1.3형 선수승
간단한 분석을 통해 규칙은 찾기가 쉽지 않고 단순한 짝관계가 아니라는 것을 발견했다(나는 짝짓기 승부관계를 잘못 내놓은 적이 있다)
(2) 우리 좀 깊이 들어가자
우리가 두 무더기를 발견했을 때, 우리는 재미있는 법칙을 찾았다. 그것은 두 무더기의 숫자가 같으면 뒷손이 이기고, 두 무더기의 숫자가 같지 않으면 먼저 손이 이기는 것이다. (왜 그런지 생각해 보자.)그러나 세 무더기는 또 통하지 않을 것 같다. 가장 간단한 1+1+1 구조라면 분명히 각 무더기의 수가 같지만 선두주자가 이겨야 하기 때문이다.그러나 우리는 곧 세 무더기의 상황에 대해 만약 각 무더기의 수량이 같다면 틀림없이 먼저 이겨야 한다는 것을 발견할 것이다.더욱 널리 보급하면 우리는 다음과 같은 결론을 얻을 수 있다.
기수 개 로 쌓였는데, 각 무더기 의 성냥 개수 가 같으니, 틀림없이 선수 가 이긴 것이다
짝수 개로 쌓였는데, 각 무더기 중의 성냥 수가 같으니, 틀림없이 뒷손이 이길 것이다
(3) 가장 까다로운 부분을 처리하기 시작한다
우리는 지금 모든 성냥더미가 같을 때의 상황을 처리할 수 있지만, 각 성냥더미는 같지 않습니까?이곳에서 우리는 수학 중의 불가사의한 관계를 다시 한 번 보았다.저희가 지금 이 게임의 승부를 재검토하고 정의하겠습니다.
(1) 누군가가 성냥을 뽑을 차례가 되면 성냥이 없어진다. 그러면 이 사람이 지면 P-구조로 한다.
(2) 누군가가 성냥을 뽑을 차례가 되면 성냥을 다 뽑을 수 있다면 이 사람이 이기면 N-구도로 세운다
(3) 누군가가 성냥을 뽑을 차례가 되면 현재 구조를 어떤 P구조로 바꿀 수 있다면 이 구조는 N-구조로 바뀐다
(4) 누군가가 성냥을 뽑을 차례가 되면 현재 구조를 특정한 P구조로 바꿀 수 없다면 이 구조는 P구조로 바뀐다
다음은 우리가 하나의 정리를 유도한다. 하나의 구조는 (x1,x2,...,xn)으로 기록되고 순서는 무관하다. 이 구조는 P-구조이고 x1^x2^...^로 기록된다.xn = 0.그중^는 비트 또는 연산에 따라
추론: 상술한 4가지 상황에 대응한다(서술의 간결함을 위해 엄격하게 증명하지 않고 결론이 정확하다고 직접 가정하고 정리를 설명하는 작업 메커니즘)
(1) (x1,x2,...,xn)에서 모두 0일 때 구조는 P-구조이고 이때 x1^x2^...^xn = 0이 (가) 됩니다.
(2) (x1,x2,...,xn) 중 하나만 0이 아니라 N-구조, 이때 x1^x2^...^xn = 0이 (가) 성립되지 않습니다.
(3) (x1,x2,...,xn)이 P-구조일 때, x1,...,xn이 0이 아닙니다.(반증법)
가령 x1^x2^...^xn=p, 그리고 p는 0이 아닙니다.
p의 2진법 표시에서 가장 왼쪽의 1(최고위의 1)은 왼쪽에서 오른쪽으로 k위를 차지한다.
p가 다른 연산의 결과이기 때문에 x1, x2,......xn에서 최소한 한 개의 수 k위는 1이고,
xi의 k위가 1이라면 xi^p위가 0이면 xi>xi^p가 분명히 성립된다.
즉, 어떤 취법이 존재하여 i더미의 성냥 수를xi^p로 변화시킨다.
제목 x1^x2^...^xn=p, 그럼 x1^x2^...^xn ^ p = 0.
그러면 현재 구조는 특정한 P-구조로 바뀔 수 있다. 즉, 현재 구조는 N-구조, 모순
그래서 반드시 p=0이 있다.
(4)x1^x2^...^xn = 0 시, 만약 어떤 이동 xi가 xi로 변한다면, x1^x2^...^xi ' ^...^xn = 0,
그렇다면 다른 연산의 소거율은 xi=xi, 즉 성냥 한 개비도 찾지 않았다는 것이다. 이것은 허용되지 않는다. 그래서
현재 구조는 P 구조만 가능합니다.
이 강력한 정리가 있으면 다음 문제는 잘 해결될 것이다.

#include <iostream>
using namespace std;

int main()
{

	int M;
	while(cin>>M)
	{
		/*input*/
		int pile[20] ={};
		for(int i=0; i<M; ++i)
		{	cin>>pile[i];	}

		/*calculate*/
		int result   = 0;
		for(int i=0; i<M; ++i)
		{	result ^= pile[i];	}

		/*output*/
		if(result)cout<<"Yes"<<endl;
		else      cout<<"No" <<endl;
	}

	return 0;
}