大吉大利【牛客网】（牛客练习赛60）

传送

时间限制：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 =2²
010对应的就是2 =2¹
001对应的就是1 =2⁰
二进制转换成十进制时要乘以对应位置2的n次方，就是4 * 2² + 4 * 2¹ + 9 * 2⁰=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;
}