线性基就是把一堆数搞成一个方便判断的小集合,使得小集合可以异或出所有原集合能异或出的数。其实很暴力的感觉,直接贴代码,每次看到都应该能想出来原理吧…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| const int MAXBIT=60; struct Xor_Base { LL a[64]; void insert(LL x) { per(i,MAXBIT,0) { if (x&(1ll<<i)) { if (a[i]) x^=a[i]; else { a[i]=x; break; } } } } LL query_max() { LL res=0; per(i,MAXBIT,0) if ((a[i]^res)>res) res^=a[i]; return res; } LL query_min() { rep(i,0,MAXBIT) if (a[i]) return a[i]; return 0; } bool can_do(LL x) { per(i,MAXBIT,0) { if (x&(1ll<<i)) { if (a[i]) x^=a[i]; else { return true; break; } } } return false; } }xb;
|