fork download
copy 
  1. #include<cstdio>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6.  
  7. int counts[1000001], dp[1000001][22], bits, maxi;	// maxi is the maximum num present in array and bits is the MSB of maxi...
  8.  
  9. void initialize(){
  10.     for(int j=0; j<1000001; j++)
  11.         counts[j] = 0;
  12.     bits = 0;
  13.     maxi = 0;
  14.     return;
  15. }
  16.  
  17. void find_bits_maxi(){
  18.     int j=1000000;
  19.     while(j >= 0 && counts[j] == 0)
  20.         j--;
  21.     maxi = j;
  22.     for(j = 22; j >= 0; j--)
  23.         if((1 << j) & maxi) break;
  24.     bits = j+1;
  25.     return;
  26. }
  27.  
  28. int reverse_bits(int n){
  29.     int a[32];
  30.     for(int j=bits - 1; j >= 0; j--)
  31.         if(n >= (1 << j)){
  32.             n -= 1 << j;
  33.             a[j] = 1;
  34.         }
  35.         else a[j] = 0;
  36.     n = 0;
  37.     for(int j=0; j < bits; j++)
  38.         if(!a[j]) n += 1 << j;
  39.     return n;
  40. }
  41.  
  42. void build_zeroth_of_dp(){
  43.     for(int j=0; j <= maxi; j++){
  44.         dp[j][0] = counts[reverse_bits(j)];
  45.     }
  46.     return;
  47. }
  48.  
  49. void solve(){
  50.     find_bits_maxi();
  51.     build_zeroth_of_dp();
  52.  
  53.     for(int j = 1; j <= bits; j++){
  54.         int curr_bit = j-1;
  55.         for(int k = maxi; k >= 0; k--)
  56.             if((1 << curr_bit) & k) dp[k][j] = dp[k][j-1];
  57.             else dp[k][j] = dp[k][j-1] + dp[ k ^ (1 << curr_bit) ][j];
  58.     }
  59.  
  60.     ll ans = 0;
  61.     for(int j = maxi; j > 0; j--)
  62.         ans += (ll)counts[j] * (ll)dp[j][bits];
  63.     ans += (ll)counts[0] * (ll)(dp[0][bits] - 1);
  64.  
  65.     printf("%lld\n",ans);
  66.     return;
  67. }
  68.  
  69. int main(){
  70.     int t;
  71.     scanf("%d",&t);
  72.     while(t--){
  73.         initialize();
  74.         int n;
  75.         scanf("%d",&n);
  76.         while(n--){
  77.             int temp;
  78.             scanf("%d",&temp);
  79.             counts[temp]++;
  80.         }
  81.         solve();
  82.     }
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0s 105920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tR8gWl
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!