Problem D: 序列异或

Problem D: 序列异或

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 84  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个长度为 n 的数组 a1,a2,a3,...,an,问有多少组满足条件的四元组 (i,j,p,q(1i<j<p<qn) 满足 ai xor aj xor ap xor aq =0
其中 xor 是异或运算。

Input

第一行一个整数 n 表示数组长度。

第二行 n 个整数 a1,a2,a3,...,an 表示数组的值。

Output

一行一个整数,表示答案。

Sample Input Copy

6
1 3 0 0 2 2

Sample Output Copy

5

HINT

样例解释:

满足条件的四元组为:(1,2,3,5),(1,2,3,6),(1,2,4,5),(1,2,4,6),(3,4,5,6)

数据范围:

共 10 组数据

对于测试点 1,2 满足 n100ai1000

对于测试点 3,4 满足 n1000,ai1000

对于测试点 5,6 满足 n5000,ai1000

对于所有测试点满足 4n5000,0ai106