985的数学难题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 const int maxn = 100005;
 8 
 9 LL wei(LL x)
10 {
11     LL k = 0;
12     while(x)      // 计算一个数的二进制位数；
13     {
14         k++;
15         x >>= 1;
16         //k++;
17     }
18     return k;
19 }
20 
21 int main()
22 {
23     int t;
24     scanf("%d",&t);
25     LL T[maxn];    //
26     LL a[maxn];
27     while(t--)
28     {
29         memset(T,0,sizeof(T));  //T[]表示一个数二进制各个位的1的个数；
30         //memset(a,0,sizeof(a));
31         LL n;
32         scanf("%d",&n);
33         LL Sum = 0;
34         LL ans = 0;
35         for(LL i = 0; i < n; i++)
36         {
37             scanf("%lld",&a[i]);
38             Sum += a[i];
39         }
40         sort(a,a+n);
41         LL _size = wei(a[n - 1]);                                        //求出最大数的二进制位数；                                         
42         //LL ans = 0;
43         for(LL i = 0; i < _size; i++)                                    //i表示二进制的位数； 
44         {
45             for(LL j = 0; j < n; j++)                                    //n个数进行操作；
46             {
47                 T[i] = (T[i] + (a[j] & 1));                              //统计每个位数上的1的个数；
48                 a[j] >>= 1;                                              //向右移位，统计下一位
；49             }
50             ans += (1 << i)*(T[i] * (n - T[i]) + T[i] * (T[i] - 1)/2);  //第i位的权重*（有1和0的情况+全是1的情况排列组合）；
51         }
52         ans *= 2;
53         ans += (Sum * (n - 1));            //对于题中的二重循环，每次两个数相加，之后每个数相加了 n-1 次，
54         printf("%lld\n",ans);
55     }
56     return 0;
57 }



/**********tips:
a^b + a&b = a|b;
***************/