fork(2) download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. signed main(){
  6. 	ios_base::sync_with_stdio(false);
  7.     cin.tie(NULL);
  8. 	// freopen("evencomb.inp", "r", stdin);
  9. 	// freopen("evencomb.out", "w", stdout);
  10.     int n; cin >> n;
  11.  
  12.     int sz = 1<<20;
  13. 	int freq[sz], dp[sz], a[n];
  14.     memset(dp, 0, sizeof dp);
  15.     memset(freq, 0, sizeof freq);
  16.     vector<int> b;
  17.     for(int i = 0; i < n; i++){
  18.     	cin >> a[i];
  19.     	freq[a[i]]++;
  20.     	if(freq[a[i]] == 1) b.push_back(a[i]);
  21.     }
  22.     for(int i = 0; i < n; i++){
  23.     	dp[a[i]] = freq[a[i]];
  24.     }
  25.     for(int i = 0; i < 20; i++){
  26.     	for(int j = 1; j < sz; j++){
  27.     		if((j >> i) & 1){
  28.     			dp[j] += dp[j ^ (1 << i)];
  29.     		}
  30.     	}
  31.     }
  32.  
  33. 	sort(b.begin(), b.end());
  34. 	int res = n * (n - 1) / 2, tmp = 0;
  35. 	for(int i = 0; i < b.size(); i++){
  36. 		res -= (dp[b[i]] - freq[b[i]]) * freq[b[i]]  +  (freq[b[i]] * (freq[b[i]] - 1) / 2);
  37. 	}
  38.     cout << res;
  39.  
  40. }
  41.  
Success #stdin #stdout 0.04s 19844KB
comments (?)
stdin 
5
8 8 3 3 4
stdout 
8
https://ideone.com/lz6HtB
language:
C++14 (clang 8.0)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!