# [Platinum IV] 님 게임 3 [문제 링크](https://www.acmicpc.net/problem/16895) ## 문제 설명 <p>구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. </p> <p>게임은 구사과가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 구사과가 게임을 이기기 위해서 첫 턴에 할 수 있는 방법의 수를 구하시오.</p> ## 입력 <p>첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 1000)이 주어진다.</p> <p>둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 P_i (1 ≤ P_i ≤ 1000)가 주어진다.</p> ## 출력 <p>구사과가 게임을 이기기 위해서 첫 턴에 할 수 있는 방법의 수를 출력한다.</p> ## 풀이 어떤 수 x를 제외한 나머지 수들의 XOR 값이 x보다 작거나 같은 경우에 그런디 수를 0으로 만들 수 있어서 첫 턴의 방법의 수가 하나씩 늘어난다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int ret=0; vector<int> p(n); for(int i=0;i<n;i++) { cin >> p[i]; ret ^= p[i]; } int cnt=0; if(ret) { for(int i=0;i<n;i++) { if((ret^p[i])<=p[i]) cnt++; } } cout << cnt; } ```