本文主要是介绍zzuli 1893 (985的数学难题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
985的数学难题
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
注意:a^b + a&b = a|b.
// ^ 不同即为1,
// | 有1则为1
// & 都是1才为1.
// & + ^ = |
/* ans+=a[i]+a[j]+2*(a[i]|a[j]);//有1就为1,判断贡献了多少1. 先算+,sum+=a[i],ans=(n-1)*sum ;然后异或运算,ans+=(cnt[0]*(n-cnt[0])+cnt[0]*(cnt[0]-1)/2 )*mu*2
*/
#include<cstdio>
#include<algorithm>
using namespace std;bool cmp(int a,int b){return a>b;
}
int main(){int t,n;long long s;int a[101001];scanf ("%d",&t);while (t--){s=0;int i;long long ans=0,sum=0;scanf ("%d",&n);for (i=1;i<=n;i++){scanf ("%d",&a[i]);sum+=a[i];}sum*=(n-1);//a[i]+a[j]long long mu=1;//注意long longsort(a+1,a+1+n,cmp);//二进制运算从大数开始 while (a[1]){ans=0;for (i=1;i<=n;i++){if (a[i]==0)break;if (a[i]&1)//末位为1 ans++; a[i]>>=1;//右移 }sum += (ans*(n-ans)+ans*(ans-1)/2)*mu*2;mu<<=1; //左移,相当于下一位运算扩大二倍 }printf ("%lld\n",sum);} return 0;
}
这篇关于zzuli 1893 (985的数学难题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!