A题题解

本蒟蒻由于明天要考试和太水了，所以只做了A题
首先解释一下A题是什么意思。
这个符号用于求和，通俗的说题目中的两个 就是for (int i=1; i<=n; i++) 和 for (int j=1; i<=n; i++)

那么题目就变得通俗易懂了，即最朴素的写法就是：

int ans = 0;
for (int i=1; i<=n; i++)
{
for (int j=1; i<=n; i++) ans += (a[i]&a[j]);
}
但不过，很显然这样是过不了的。这样子的复杂度达到了O(n²)，n<=1e5，显然会TLE。
那么这时候就要用到群友们的xjb搞搞大法

首先，以样例为例子，我们将每个数字转换成二进制，则为：
001
010
011
100
101
&的规则是：如果1&1则返回1，否则返回0.
那么在刚刚的二重循环中，我们可以发现，每个数字的1都所在的列的1（包括自己）进行了一遍“&”运算
比如以第三行为例：
1
0
1
0
1
则第一个1与所有的1进行“&”运算完后得到3，第二个与所有的1进行“&”运算后再得到3......
这时候，规律已经很明显了，当行数字所有的“&”运算结果加起来就是1的数目的平方！
这时候，只要把每一行的1的个数算出来再进行平方就可以了
【等等，好像少了什么】
因为是2进制，我们还得把最终结果转换回十进制。所以吧刚才每行算出来的1的个数的平方再乘以2的i次方就可以了（相信大家都知道i从右往左数）
那么这时候样例的计算结果就是
ans = 33(2^0) + 22(2^1) + 22(2^2) = 33！
这里贴上AC代码

#include<bits/stdc++.h>
using namespace std;
long long a[1005], ans=0;

long long pow(int base, int n)
{
    long long sum=1;
    while (n)
    {
        if (n&1) sum = base*sum;
        base *= base;
        n >>= 1;
    }
    return sum;
}

int main()
{
    long long n, maxc=0; scanf("%lld", &n);
    for (int i=1; i<=n; i++)
    {
        long long num, cnt=0, nm; scanf("%lld", &num);
        while (num)
        {
            if (num&1)     a[cnt] ++;
            cnt++;
            num >>= 1;
        }
        maxc = max(maxc, cnt);
    }
    for (int i=0; i<maxc; i++) ans += a[i]*a[i]*pow(2, i);
    printf("%lld", ans);
}