님 게임 3

• 스프라그-그런디 정리 를 이용하는 기본적인 문제. Nim와도 동일한 문제.
• 정리에 따르면, 그런디 수가 0이 아니면 선공이 무조건 이길수 있는 방법이 존재하고, 그 방법은 그런디 수를 0으로 만드는 행동을 하는 것이다. 여기서도 그런디수를 0으로 만들수 있는 행동의 갯수를 구하면 된다.
• 처음 상태의 그런디수 g= p1^p2^…^pN 이고, 여기에서 i번째 무더기를 골라서 k개의 돌을 뺐을때의 그런디 수는, g^pi^(pi-k)이다. 이값이 0이 되려면 g^pi 와 (pi-k)가 같아야 한다. 따라서 이런 k는 g^pi가 pi보다 크거나 같으면 존재하지 않고, g^pi가 pi보다 작을때만 1개 존재한다.
• g^pi < pi 인 무더기에 대해서만 그 무더기에서 돌을 제거해서 이길수 있는 방법이 1개 존재한다. 결국 답은 g^pi < pi 인 무더기의 갯수를 세면 구할수 있다. 시간 복잡도는 O(n)

"""Solution code for "BOJ 16895. 님 게임 3".

- Problem link: https://www.acmicpc.net/problem/16895
- Solution link: http://www.teferi.net/ps/problems/boj/16895

Tags: [Sprague-Grundy]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    P = [int(x) for x in input().split()]

    grundy = 0
    for p_i in P:
        grundy ^= p_i
    answer = sum(1 for p_i in P if grundy ^ p_i < p_i)
    print(answer)


if __name__ == '__main__':
    main()