本文主要是介绍UESTC--1041--Hug the princess(位运算),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Hug the princess
Time Limit: 1000MS | Memory Limit: 65535KB | 64bit IO Format: %lld & %llu |
Description
There is a sequence with n elements. Assuming they are a1,a2,⋯,an.
Please calculate the following expession.
∑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 n, which is the size of the sequence.
The second line contains n integers, the ith integer ai is the ith element of the sequence.
1≤n≤100000,0≤ai≤100000000
Output
Print the answer in one line.
Sample Input
2
1 2
Sample Output
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”.
Source
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 100;
int num[MAXN][35];
int a[35];
int p[MAXN];
typedef long long LL;
int main()
{int n;while(~scanf("%d", &n)){int x;memset(num, 0, sizeof(num));for(int i = 1; i <= n; i++){scanf("%d", &x);for(int j = 0; j < 33; j++){num[i][j] = num[i - 1][j] + x % 2;x = x / 2;}}LL ans = 0;for(int i = 1; i <= n; i++){int temp = 0, pos = -1;for(int j = 0; j < 33; j++){a[j] = num[i][j] - num[i - 1][j];}for(int j = 0; j < 33; j++){int cnt = 0;if(a[j]){cnt += (i - 1 - num[i - 1][j]);cnt += i - 1;cnt += num[i - 1][j];}else{cnt += num[i - 1][j];cnt += num[i - 1][j];}ans += (LL)cnt * (1 << j);}}printf("%lld\n", ans);}return 0;
}
这篇关于UESTC--1041--Hug the princess(位运算)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!