1893: 985的数学难题

1893: 985的数学难题

Time Limit: 2 Sec   Memory Limit: 128 MB Submit: 174   Solved: 43 Submit Status Web 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

211021 1

Sample Output

04

HINT

Source

题意即为n个数，两两相加，相或，相与，相异或，求最后的和。 #include<stdio.h> #include<algorithm> using namespace std; bool cmp(long long a,long long b) { return a>b; } int main() { int t,n,i; long long ans,sum,ant; long long a[100010]; scanf("%d",&t); while(t--) { scanf("%d",&n); sum=0; ans=0; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); sum+=a[i]; } ans+=sum*(n-1); sort(a+1,a+1+n,cmp); int m=1;\\判断在2进制的哪一位 while(a[1]) { ant=0; for(i=1;i<=n;i++) { if(a[i]&1) ant++; a[i]>>=1; } ans+=m*(ant*(ant-1)>>1); \\相与，只有两两都为1结果才为一 ans+=((n-ant)*ant+(ant*(ant-1)>>1))*m;\\相或， ans+=(n-ant)*ant*m;\\相异或 m<<=1; } printf("%lld\n",ans); } return 0; }