传送

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format:%lld

题目描述

输入描述:

第一行一个整数n.
第二行n个整数ai.

输出描述:

一个整数表示上述求和式的答案.
示例1
输入

5
1 2 3 4 5

输出

33

备注:
1≤n≤1e5
0≤ai≤1e8

题解:
根据题意就能打出最简单的暴力方法
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
sum+=a[i]&a[j];
复杂度O(n)肯定超时,这题也不可能这么水。

---------------------------------(此处为做题时错误想法)
我一开始这么想的a[i]&a[j] = = a[j]&a[i],所以j循环时从i+1开始就行,因为这个是对称的,sum算完再*2,最后再加上对角线上的i = = j的情况,结果还是超时(捂脸
<mark>(以下为正解)</mark>
&啥性质?1&1=1,其余情况都为0
当1&2是,我们可以转化成二进制运算,01&11=01
其实就是对应列&运算,
0 1
&
1 1
——
0 1
我们看样例:
1 ->0 0 1
2 ->0 1 0
3 ->0 1 1
4 ->1 0 0
5 ->1 0 1
看第一列:
0
0
0
1
1
因为0&任何都是0,所以看1,第四五行有1,
那运算时第四行&第四行=1,第四行&第五行=1,接着第五行再分别与第五行和第四行&运算也是两个1,最后加起来一共四个1.其实就是这一列1的数量的平方。你试试最后一列是不是也是这样?
(其实这个就是模仿暴力方法的第二个for循环,i与每个j&运算)
那这样算例题,结果就是
1 ->0 0 1
2 ->0 1 0
3 ->0 1 1
4 ->1 0 0
5 ->1 0 1
结果->4 4 9
这个449就可以理解成有4个100,4个010,9个001,因为咱们是用二进制运算,要转换成十进制,
100对应的就是4 =22
010对应的就是2 =21
001对应的就是1 =20
二进制转换成十进制时要乘以对应位置2的n次方,就是4 * 22 + 4 * 21 + 9 * 20=33
33就是最后结果(各位想明白了吗?
代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[10004];
ll w;
ll maxn;
int max(ll a,ll b)
{
   
	return a>b?a:b;
}
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)
	{
   
		int ant=0;
		cin>>w;
		while(w)
		{
   
			++ant;
			if(w&1)a[ant]++;//求出每列1的数量 
			w>>=1;
			
		}
		maxn=max(ant,maxn);//确定一共有多少列 
	}
	ll sum=0;
	for(int i=1;i<=maxn;i++)
	sum+=(a[i]*a[i])<<(i-1);
	cout<<sum;
	return 0;
}