Guest User

K - Counting Good Teams

a guest
Aug 29th, 2017
230
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9.  
  10. ll v1[1<<22];
  11. ll v2[1<<22];
  12. ll eq[1<<22];
  13. vi v;
  14.  
  15. int main() {
  16.     ll n, m;
  17.     cin >> n >> m; 
  18.     for(int i = 0; i < n; i++) {
  19.         int aux;
  20.         cin >> aux;
  21.         v.pb(aux);
  22.     }
  23.     int h1 = m/2;
  24.     int h2 = m - h1;
  25.     for(int i = 0; i < n; i++) {
  26.         int h1mask = v[i] >> h2;
  27.         h1mask = h1mask << h2;
  28.         int h2mask = ((1 << h2) - 1) & v[i];
  29.         int h2maskcp = ((1 << h2) - 1) & (~h2mask);
  30.  
  31.         for(int j = h1mask; j; j = (j - 1)&h1mask){
  32.             v1[j + h2mask]++;
  33.         }
  34.         v1[h2mask]++;
  35.         for(int j = h2maskcp; j; j = (j - 1)&h2maskcp){
  36.             v2[j + h2mask + h1mask]++;
  37.         }
  38.         v2[h2mask + h1mask]++;
  39.         eq[v[i]]++;
  40.     }
  41.     ll ans = 0;
  42.     for(int i = 0; i < (1 << m); i++) {
  43.         ans += v1[i]*v2[i];
  44.         ans -= (eq[i]*(eq[i]-1))/2;
  45.     }
  46.     ans -= n;
  47.     cout << (n * (n-1))/2 - ans << endl;
  48.     return 0;
  49. }
RAW Paste Data