스프러그-그런디 [16895]

[1. 문제 설명]

https://www.acmicpc.net/problem/16895

---

[2. 풀이 접근]

최초 상태에서 필패하는지 먼저 확인 한다.

• 필패 하면, 이기기 위해 첫턴에 할 수 있는 경우의 수는 존재하지 않는다.

이길 수 있는 상황이라면,

• n 번째 돌무더기를 제외하고, 그런디 수를 계산한다.
• n 번째 돌무더기에서, 위에서 계산한 그런디 수로 만들게 끔 돌을 가져갈 수 있는지 확인한다.
• Value ^ Value = 0, 이므로 첫번째 턴에서 돌을 가져가서 전체 그러딘 수를 0으로 만들면,
• 다음턴에 상대는 필패하게 된다.

하나이상 제거가 반드시 발생하기 때문에, 아무것도 하지 않는 경우는 발생할 수 없다.

그러나, 아무것도 하지 않는 경우는 이미 고려되었기 때문에,

• if (v == 0) return 0;

아래 조건문에서 등호가 성립하는 경우는 발생하지 않는다. (등호를 생략해도 됨)

• if (Pi[i] >= v) result++;

---

[3. 코드]