Hug the princess
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
There is a sequence with nn elements. Assuming they are a1,a2,⋯,ana1,a2,⋯,an.
Please calculate the following expession.
∑1≤i<j≤n(ai∧aj)+(ai|aj)+(ai&aj)∑1≤i<j≤n(ai∧aj)+(ai|aj)+(ai&aj)
In the expression above, ^ | & is bit operation. If you don’t know bit operation, you can visit
http://en.wikipedia.org/wiki/Bitwise_operation
to get some useful information.
Input
The first line contains a single integer nn, which is the size of the sequence.
The second line contains nn integers, the ithith integer aiai is the ithith element of the sequence.
1≤n≤100000,0≤ai≤1000000001≤n≤100000,0≤ai≤100000000
Output
Print the answer in one line.
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 |
6 |
Hint
Because the answer is so large, please use long long instead of int. Correspondingly, please use %lld instead of %d to scanf and printf.
Large input. You may get Time Limit Exceeded if you use "cin" to get the input. So "scanf" is suggested.
Likewise, you are supposed to use "printf" instead of "cout".
题解：
让求这个表达式，我们可以把求出每一位的前缀和，然后再根据每一位找出前面是1，是0的当前位的个数；然后加上cnt * (1 << j)就好了
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + ;
int num[MAXN][];
int a[];
int p[MAXN];
typedef long long LL;
int main(){
int n;
while(~scanf("%d", &n)){
int x;
memset(num, , sizeof(num));
for(int i = ; i <= n; i++){
scanf("%d", &x);
for(int j = ; j < ; j++){
num[i][j] = num[i - ][j] + x % ;
x = x / ;
}
}
LL ans = ;
for(int i = ; i <= n; i++){
int temp = , pos = -;
for(int j = ; j < ; j++){
a[j] = num[i][j] - num[i - ][j];
// printf("%d ", a[j]);
}//puts("");
for(int j = ; j < ; j++){
int cnt = ;
if(a[j]){
cnt += (i - - num[i - ][j]);
cnt += i - ;
cnt += num[i - ][j];
}
else{
cnt += num[i - ][j];
cnt += num[i - ][j];
}
ans += (LL)cnt * ( << j);
}
}
printf("%lld\n", ans);
}
return ;
}