#P17037. [SGU542] Gena 对 Petya

    ID: 16281 传统题 1500ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-Nim数位 DP状态维度消除基数排序一维前缀和滚动数组

[SGU542] Gena 对 Petya

题目描述

Gena 和 Petya 玩 Nim 游戏。桌上有 nn 堆石子,第 ii 堆有 aia_i 个石子。两人轮流操作,Gena 先手。每次操作选择一个非空石子堆并从中拿走任意正数个石子;无法操作的人失败。

两人都会采用最优策略。

Petya 觉得 Gena 总是先手不公平,于是决定在游戏开始前偷偷从每一堆中拿走相同数量的石子。设拿走的数量为 xx,要求:

0≤x<min⁡iai0\le x<\min_i a_i。

拿走之后,第 ii 堆剩余 ai−xa_i-x 个石子,然后由 Gena 先手开始正常 Nim 游戏。

求有多少个不同的整数 xx 能使 Petya 在双方最优策略下获胜。

输入格式

第一行一个整数 nn,1≤n≤2×1051\le n\le2\times10^5。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,1≤ai≤10181\le a_i\le10^{18}。

输出格式

输出一个整数,表示满足条件的 xx 的数量。

样例 1

样例输入

2
3 3

样例输出

3

样例 2

样例输入

3
3 4 5

样例输出

1

样例 3

样例输入

4
2 7 4 1

样例输出

1

样例 4

样例输入

4
4 6 8 10

样例输出

2

样例说明

第一组样例中 x=0,1,2x=0,1,2 均可使两堆石子保持相等,因此 Petya 获胜。第二组样例唯一可行的 xx 为 22;第三组为 00;第四组为 00 和 33。