【Codeforces 1420 B】Rock and Lever，位运算，找规律

problem

B. Rock and Lever
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
“You must lift the dam. With a lever. I will give it to you.
You must block the canal. With a rock. I will not give the rock to you.”

Danik urgently needs rock and lever! Obviously, the easiest way to get these things is to ask Hermit Lizard for them.

Hermit Lizard agreed to give Danik the lever. But to get a stone, Danik needs to solve the following task.

You are given a positive integer n, and an array a of positive integers. The task is to calculate the number of such pairs (i,j) that i<j and ai & aj≥ai⊕aj, where & denotes the bitwise AND operation, and ⊕ denotes the bitwise XOR operation.

Danik has solved this task. But can you solve it?

Input
Each test contains multiple test cases.

The first line contains one positive integer t (1≤t≤10) denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer n (1≤n≤105) — length of the array.

The second line contains n positive integers ai (1≤ai≤109) — elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output
For every test case print one non-negative integer — the answer to the problem.

Example
inputCopy
5
5
1 4 3 7 10
3
1 1 1
4
6 2 5 3
2
2 4
1
1
outputCopy
1
3
2
0
0
Note
In the first test case there is only one pair: (4,7): for it 4 & 7=4, and 4⊕7=3.

In the second test case all pairs are good.

In the third test case there are two pairs: (6,5) and (2,3).

In the fourth test case there are no good pairs.

B.摇滚与杠杆
每次测试的时限1秒
每个测试的内存限制256 MB
输入标准输入
输出标准输出
“您必须提起水坝。用杠杆。我将它交给您。
您必须堵住运河。用一块石头。我不会把石头给你。”

Danik迫切需要坚如磐石！显然，获得这些东西的最简单方法是向隐士蜥蜴索取。

隐士蜥蜴同意给予丹尼克杠杆。但是，要想获得成功，Danik需要解决以下任务。

给您一个正整数n和一个正整数数组a。任务是计算i <j和ai＆aj≥ai⊕aj的对（i，j）的数量，其中＆表示按位与运算，⊕表示按位XOR运算。

Danik解决了此任务。但是你能解决吗？

输入项
每个测试包含多个测试用例。

第一行包含一个正整数t（1≤t≤10），表示测试用例的数量。测试用例的说明如下。

每个测试用例的第一行包含一个正整数n（1≤n≤105）-数组的长度。

第二行包含n个正整数ai（1≤ai≤109）-数组的元素。

保证所有测试用例的n之和不超过105。

输出量
为每个测试用例打印一个非负整数—问题的答案。

例
inputCopy
5
5
1 4 3 7 10
3
1 1 1
4
6 2 5 3
2
2 4
1个
1个
outputCopy
1个
3
2
0
0
注意
在第一个测试用例中，只有一对：（4,7）：4＆7 = 4，4⊕7= 3。

在第二个测试用例中，所有对都是好的。

在第三个测试用例中，有两对：（6,5）和（2,3）。

在第四个测试用例中，没有好的对。

Let’s take a pair (ai,aj) and see in which case ai & aj≥ai⊕aj will hold. For this we will follow the bits ai and aj from highest to lowest. If we meet two zero bits, the values of ai & aj and ai⊕aj will match in this bit, so we move on. If we meet a zero bit in ai and in aj —one bit(or vice versa), then we get ai & aj<ai⊕aj, and we can immediately say that the required condition is false. And if we meet two one bits, then the required condition is fulfilled, e. ai & aj>ai⊕aj, and then the bits can no longer be considered.

Now let’s consider the highest one bit in the number of ai (let it stand at pi position) and the highest single bit in the number of aj (let it stand at pj position). (Here, we consider that the bits are numbered in order of lowest to highest.) Then, pi=pj must hold. If pi>pj, then there is zero in the aj position and one unit in the ai position. But then from the reasoning above we get that ai & aj<ai⊕aj. The case of pi<pj is treated in a similar way.

It is also easy to see that if pi=pj then we automatically get the condition ai & aj>ai⊕aj.

From here the problem is solved. For each number we find the position of the highest one bit pi. Then we need to calculate the number of pairs of numbers, for which pi=pj. You may notice that the answer is ∑ℓkℓ⋅(kℓ−1)2, where kℓ — the number of numbers for which pi=pj.

The complexity of the solution is O(n).

让我们取一对（ai，aj），看看在哪种情况下ai＆aj≥ai⊕aj会成立。为此，我们将从最高到最低跟随ai和aj位。如果我们遇到两个零位，则ai＆aj和ai⊕aj的值将在此位匹配，因此我们继续。如果我们在ai和aj中都遇到一个零位-一位（或者反之亦然），那么我们得到ai＆aj <ai⊕aj，我们可以立即说出所需条件为假。如果我们满足两个一位，则满足所需条件，例如e。 ai＆aj>ai⊕aj，然后不再考虑这些位。

现在，让我们考虑ai数的最高一位（让它位于pi位置）和aj数的最高单一位（让它站在pj位置）。 （在这里，我们认为这些位是按从低到高的顺序编号的。）然后，pi = pj必须成立。如果pi> pj，则aj位置为零，ai位置为1个单位。但是从上面的推理中我们得到了ai＆aj <ai⊕aj。 pi <pj的情况以类似方式处理。

还很容易看到，如果pi = pj，则我们自动获得条件ai＆aj>ai⊕aj。

从这里解决问题。对于每个数字，我们找到最高位pi的位置。然后我们需要计算数字对的数量，其中pi = pj。您可能会注意到答案是∑ℓkℓ⋅（kℓ−1）2，其中kℓ-pi = pj的数字数。

解决方案的复杂度为O（n）。

solution

/*
题意：
+ 给出一个长为n（<1e5）的数组
+ 统计有几对(i,j)满足ai&aj>ai^aj
思路：
+ &是相同为1，^是相反为1。对于2个数(i,j),因为&和^都是逐位生成的，所以关键在于比较最高位。
+ 可以发现，当且仅当i的最高位1和j的最高位1位置相同时，满足1&1>1^1，否则1&0<1^0或0&1<0^1.
+ 所以枚举第i位为1的数有几个，相互之间构成对数+=n*(n-1)/2，复杂度为O(n)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int a[maxn];
int main(){
	int T;  cin>>T;
	while(T--){
		int n;  cin>>n;
		for(int i = 0; i < n; i++)
			cin>>a[i];
		LL ans = 0;
		for(int j = 30; j >= 0; j--){//int最多第31位，32位是符号位
			LL cnt = 0;
			for(int i = 0; i < n; i++){
				if(a[i]>=(1<<j) && a[i]<(1<<(j+1))){//如果第j位为1,累加
					cnt++;
				}
			}
			ans += cnt*(cnt-1)/2;
		}
		cout<<ans<<"\n";
	}
	return 0;
}