kth smallest subset xor, 1st is 0
| 42 | } |
| 43 | // kth smallest subset xor, 1st is 0 |
| 44 | T kth(T k) { |
| 45 | if (k < 1 || k > ((T)1 << sz)) { |
| 46 | return -1; |
| 47 | } |
| 48 | T x = 0; |
| 49 | T cnt = ((T)1 << sz); |
| 50 | for (int i = B - 1; i >= 0; i--) { |
| 51 | if (basis[i]) { |
| 52 | if (k > (cnt >> 1)) { |
| 53 | // set the ith bit |
| 54 | if (!(x >> i & 1)) { |
| 55 | x ^= basis[i]; |
| 56 | } |
| 57 | k -= (cnt >> 1); |
| 58 | } else { |
| 59 | // unset the ith bit |
| 60 | if (x >> i & 1) { |
| 61 | x ^= basis[i]; |
| 62 | } |
| 63 | } |
| 64 | cnt >>= 1; |
| 65 | } |
| 66 | } |
| 67 | return x; |
| 68 | } |
| 69 | // number of subsets having xor < x |
| 70 | T count_lt(T x) { |
| 71 | if (x < 0) { |