时间限制：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;
}
京公网安备 11010502036488号