fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <iostream>
  5. #include <set>
  6. #include <algorithm>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. int N, M;
  12.  
  13. int tn[2097152] = {0};
  14. int res[1048576][20];
  15.  
  16. inline int input()
  17. {
  18.     scanf("%d", &M);
  19.     int idx = 1;
  20.     tn[idx]++;
  21.     for(; M > 0; M /= 2) {
  22.         idx *= 2;
  23.         if(M & 1) {
  24.             idx++;
  25.         }
  26.         tn[idx]++;
  27.     }
  28.     return 0;
  29. }
  30.  
  31. int run(int k, int bit_move, int idx)
  32. {
  33.     int bit_flag = 1 << bit_move;
  34.     if(res[k][bit_move] >= 0) {
  35.         return res[k][bit_move];
  36.     }
  37.     //printf("run %d\n", k);
  38.     int ori = k;
  39.     int bit = bit_flag;
  40.     int bit_bit = bit_move;
  41.     int result = 0;
  42.     for(; k >= bit; bit *= 2, bit_bit++) {
  43.         //printf("ori %d k %d idx %d\n", ori, k, idx);
  44.         idx *= 2;
  45.         if(k & 1) {
  46.             ++idx;
  47.             if(tn[idx] == 0) {
  48.                 res[ori][bit_move] = result;
  49.                 return result;
  50.             }
  51.         } else {
  52.             //printf("ori %d plus [%d]\n", ori, (ori | bit));
  53.             if(bit >= bit_flag) {
  54.                 result += run((ori | bit), bit_bit, idx + 1);
  55.             }
  56.             if(tn[idx] == 0) {
  57.                 res[ori][bit_move] = result;
  58.                 return result;
  59.             }
  60.         }
  61.     }
  62.     result += tn[idx];
  63.     res[ori][bit_move] = result;
  64.     return result;
  65. }
  66.  
  67. // int re(int n)
  68. // {
  69. //     unsigned int k = n;
  70. //     k = ~k;
  71. //     n = 0;
  72. //     for(int i = 0; i < 20; ++i, k /= 2) {
  73. //         n *= 2;
  74. //         n += (k & 1);
  75. //     }
  76. //     return n;
  77. // }
  78.  
  79. int main()
  80. {
  81.     memset(res, -1, sizeof(res));
  82.     memset(tn, 0, sizeof(tn));
  83.  
  84.     scanf("%d", &N);
  85.     for(int i = 0; i < N; ++i) {
  86.         input();
  87.     }
  88.  
  89.     //run(1048576, 0);
  90.     //printf("%d\n", run(4, 0));
  91.  
  92.     // for(int i = 0; i < 16; ++i) {
  93.     //     printf("%d\n", re(i));
  94.     // }
  95.  
  96.     for(int i = 0; i < 1048576; ++i) {
  97.         run(i, 0, 1);
  98.     }
  99.     for(int i = 0; i < 16; ++i) {
  100.     //for(int i = 0; i < 1000001; ++i) {
  101.         printf("%d\n", res[i][0]);
  102.     }
  103.     return 0;
  104. }
  105.  
  106.  
  107.  
Runtime error #stdin #stdout 0.1s 101312KB
comments (?)
stdin
copy 
3
2 3 3
stdout
copy 
Standard output is empty
https://ideone.com/y0seqc
language:
C++14 (gcc 8.3)
created:
8 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!