设 A 和 B 的二进制表示为 an,an−1,⋯,a1 和 bn,bn−1,⋯,b1 ,其中 ai,bi∈{0,1} ,
则它们的差异值为 ∑i=1n(ai∧bi)2i−1 ,
相似值为 ∑i=1n(ai & bi)2i−1 , 其中 ∧ 表示异或运算, & 表示与运算。
给定 n 个正整数 A1,A2,⋯,An ,求满足 Ai 和 Aj 的差异值大于相似值的 (i,j) 对数,其中 0≤i<j<n 。
输入第一行为一个整数 n ,表示数组的大小。
输入第二行为 n 个整数,第 i 个元素为 Ai 。
1≤n≤105 , 1≤Ai≤230
输出为一个整数,表示满足差异值大于相似值的对数。
输入
4
4 3 5 2
输出
4
样例解释
有如下4组数据符合条件: (1,2),(1,3),(2,4),(3,4).
输入
5
1 2 3 4 5
输出
8
样例解释
有如下8组数据符合条件: $(1 , 2),(1 , 3),(1 , 4),(1 , 5),(2 , 4),(2 , 5),(3 , 4),(3 , 5).$
输入
5
16 36 35 40 2
输出
7
样例解释
有如下7组数据符合条件: $(1 , 2),(1 , 3),(1 , 4),(1 , 5),(2 , 5),(3 , 5),(4 , 5).$
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.