??
1893: 985的数学难题
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 190 Solved: 49
SubmitStatusWeb Board
Description
985有n个正整数，他想快速知道下面函数的返回值
int a[N+1];
long long Solve() {
int i, j;
long long ans = 0;
for(i = 1; i <= N; i++) {
for(int j = i + 1; j <= N; j++) {
ans += a[i] + a[j] + (a[i] ^ a[j]) + (a[i] | a[j]) + (a[i] & a[j]);
}
}
return ans;
}
注：^表示异或运算。
Input
第一行输入一个整数t，代表有t组测试数据。
每组数据第一行输入一个整数代表元素个数，接下来一行输入n个正整数a[]。
注：1 <= t <= 30，1 <= n，a[] <= 100000。
Output
一个整数代表最后的返回值ans。
Sample Input
2
1
10
2
1 1
Sample Output
0
4
HINT
Source
hpu
思路：可以分别计算与 或 异或 也可以算出或，乘以2；
代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
int cmp(int x,int y)
{return x>y;
}
int a[100010];
int main()
{int t,n;scanf("%d",&t);while(t--){long long sum=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}sum*=(n-1);sort(a+1,a+1+n,cmp);long long m=1;while(a[1]){long long ant=0;//要用long long 否则会出错； for(int i=1;i<=n;i++){if(a[i]&1) ant++;a[i]>>=1;}/*sum+=((n-ant)*ant+(ant-1)*ant/2)*m;//或运算；sum+=ant*(ant-1)/2*m;//与运算； sum+=(n-ant)*ant*m;//异或运算； */sum+=2*((n-ant)*ant+ant*(ant-1)/2)*m;//1个数的与运算+异或运算等于这个数的或运算，直接或运算的2倍； m<<=1;}printf("%lld\n",sum);}return 0;}