fork download
  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.  
Time limit exceeded #stdin #stdout 5s 16800KB
stdin
Standard input is empty
stdout
Standard output is empty