问题描述
985的数学难题
时间限制：2 Sec内存限制：128 MB
Description
985有n个正整数，他想快速知道下面函数的返回值
1
2
3
4
5
6
7
8
9
10
11
| 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;
}
|
注：^表示异或运算。
第一行输入一个整数t，代表有t组测试数据。
每组数据第一行输入一个整数代表元素个数，接下来一行输入n个正整数a[]。
注：1 <= t <= 30，1 <= n，a[] <= 100000。
Output
一个整数代表最后的返回值ans。
2
1
10
2
1 1
Sample Output
0
4
问题分析
很显然不能直接写函数计算
这种类型的题目涉及到二进制运算
有定理
x^y+x&y==x|y
考虑二进制的每一位对结果的影响
比如1101、1001、1010进行上述运算
则可发现
从右到左每一位上有1的个数记为
cnt[0]~cnt[3]分别为
2、1、1、3
因为或运算除了0|0==0
其余都为1
也就是0|1+1|1
所以对于最右边运算后有效的1个数
为 cnt[0](n-cnt[0])+(cnt[0](cnt[0]-1))/2
而这些1所代表的个数要转变为十进制
则要乘上其对应的1«0
所以核心代码为
1
2
3
| for(int i=0; i<lx; i++) {
res+=(1<<i)*(cnt[0][i]*cnt[1][i]+(cnt[1][i]-1)*cnt[1][i]/2);
}
|
其中lx代表最大数的二进制位数
至于求a[i]+a[j]
只需要把a[1~n]相加求和之后乘(n-1)
也就是每个数用了n-1次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[100200];
int main() {
int T;
scanf("%d",&T);
while(T--) {
int n;
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%d",&a[i]);
}
sort(a,a+n);
long long cnt[2][50];
int lx=0;
memset(cnt,0,sizeof(cnt));
for(; a[n-1]>>lx!=0; lx++)
for(int i=0; i<n; i++)
cnt[a[i]>>lx&1][lx]++;
long long res=0;
for(int i=0; i<lx; i++) {
res+=(1<<i)*(cnt[0][i]*cnt[1][i]+(cnt[1][i]-1)*cnt[1][i]/2);
}
res*=2;
for(int i=0; i<n; i++) {
res+=(n-1)*a[i];
}
printf("%lld\n",res);
}
return 0;
}
|
题目地址: 【郑轻】[1893]985的数学难题