fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. typedef long long ll;
  5. ll a[200005];
  6. map<ll,ll>freq;
  7. int main()
  8. {
  9.     int n,k;
  10.     cin>>n>>k;
  11.     int fff=0;
  12.     for(int i=0;i<n;i++)
  13.     {
  14.         cin>>a[i];
  15.     }
  16.     freq[0]++;
  17.     ll aa,bb=0;
  18.     ll curr=0;
  19.     for(int i=0;i<n;i++)
  20.     {
  21.         aa = curr;
  22.         bb=0;
  23.         for(int j=0;j<k;j++)
  24.         {
  25.             if((a[i]&(1<<j)))
  26.             {
  27.                 aa^=(1<<j);
  28.             }
  29.         }
  30.         for(int j=0;j<k;j++)
  31.         {
  32.             if(!(aa&(1<<j)))
  33.             {
  34.                 bb|=(1<<j);
  35.             }
  36.         }
  37.         if(freq[aa]<freq[bb])
  38.         {
  39.             freq[aa]++;
  40.             curr = aa;
  41.         }
  42.         else
  43.         {
  44.             curr = bb;
  45.             freq[bb]++;
  46.         }
  47.         //curr = aa;
  48.     }
  49.     map<ll,ll>::iterator it = freq.begin();
  50.     ll sum=0;
  51.     for(;it!=freq.end();it++)
  52.     {
  53.  
  54.         ll ff = it->second;
  55.         sum = sum+1LL*(ff)*(ff-1)/2;
  56.     }
  57.     ll fin = 1LL*n*(n+1)/2;
  58.     cout<<fin-sum<<endl;
  59. }
  60.  
Success #stdin #stdout 0s 16800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
99325681273442253
https://ideone.com/xzo4pe
language:
C++14 (gcc 8.3)
created:
6 years 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!