Luogu P7627 题解

这题其实不难

但如果用暴力，肯定过不了

所以我们得想另一种办法

我们发现，只有 \(1\) 异或 \(0\) 的值为 \(1\)

例如：

\(1\) , \(0\) , \(1\) 两两异或的和为 2

其实就是每个 \(0\) 与每一个 \(1\) 异或时，\(sum\) 要加 \(1\)

所以，我们只要把每一位的 \(0\) 和 \(1\) 的数量都统计出来，再进行运算，就可以快速得出 \(sum\)

\(AC\hspace{0.2cm}Code\)

#include<bits/stdc++.h>//万能头文件
#define int long long//记得开 long long
using namespace std;
int n,cnt[100],sum;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int a,j=1;
		scanf("%lld",&a);
		while(a){
			cnt[j]+=a%2;//统计每一位 1 的个数
			j++;
			a/=2;
		}
	}
	for(int i=1;i<=30;i++){
		sum+=cnt[i]*(n-cnt[i])*(1<<(i-1));//算出每一位的异或值
	}
	printf("%lld",sum);
	return 0;//完美收尾
}