线性基是一种擅长处理异或问题的数据结构
一个线性基满足，对于它所表示的所有数的集合 S S S， S S S 中任意多个数异或所得的结果均能表示为线性基中的元素互相异或的结果，即线性基能使用异或运算来表示原数集使用异或运算能表示的所有数。运用这个性质，我们可以极大地缩小异或操作所需的查询次数。
P3812 【模板】线性基
code：
#include#define endl 'n'#define ll long long#define ull unsigned long long#define ld long double#define all(x) x.begin(), x.end()#define eps 1e-6using namespace std;const int maxn = 2e6 + 9;const int mod = 1e9 + 7;const int inf = 0x3f3f3f3f;const ll INF = 0x3f3f3f3f3f3f3f3f;ll n, m;ll a[100], tmp[100];// a是原线性基，tmp是重构后的线性基，用来查询第k小bool f;//可以表示0int cnt;void Insert(ll x){for(int i = 60; i >= 0; --i) if(x & (1ll << i)){if(!a[i]){a[i] = x;return;}else x ^= a[i];}f = 1;}bool check(ll x){//判断能否通过原数列异或得到一个数xfor(int i = 60; i >= 0; --i) if(x & (1ll << i)){if(!a[i]) return 0;else x ^= a[i];}return 1;}ll qmax(ll ans = 0){//查询异或最值for(int i = 60; i >= 0; --i)ans = max(ans, ans ^ a[i]);return ans;}ll qmin(){//查询异或最值if(f) return 0;for(int i = 0; i <= 60; ++i) if(a[i]) return a[i];return INF;}void rebuild(){for(int i = 0; i <= 60; ++i){for(int j = i - 1; j >= 0; --j) if(a[i] & (1ll << j))a[i] ^= a[j];if(a[i]) tmp[cnt++] = a[i];}}ll qry(ll k){// 查询第k小if(f) --k;if(!k) return 0;if(k >= (1ll << cnt)) return -1;ll ans = 0;for(int i = 0; i < cnt; ++i) if(k & (1ll << i))ans ^= tmp[i];return ans;}void work(){cin >> n;for(int i = 1; i <= n; ++i){ll x;cin >> x;Insert(x);}rebuild();cout << qmax() << endl;}int main(){ios::sync_with_stdio(0);//int TT;cin>>TT;while(TT--)work();return 0;}
牛牛数数
思路：
线性基+二分
找到第一个大于 k k k 的数的位置
再用总数减一下就可以了
code：
#include#define endl 'n'#define ll long long#define ull unsigned long long#define ld long double#define all(x) x.begin(), x.end()#define eps 1e-6using namespace std;const int maxn = 2e6 + 9;const int mod = 1e9 + 7;const int inf = 0x3f3f3f3f;const ll INF = 0x3f3f3f3f3f3f3f3f;ll n, m;ll a[100], tmp[100];bool f;//可以表示0int cnt;void Insert(ll x){for(int i = 60; i >= 0; --i) if(x & (1ll << i)){if(!a[i]){a[i] = x;return;}else x ^= a[i];}f = 1;}bool check(ll x){for(int i = 60; i >= 0; --i) if(x & (1ll << i)){if(!a[i]) return 0;else x ^= a[i];}return 1;}ll qmax(ll ans = 0){for(int i = 60; i >= 0; --i)ans = max(ans, ans ^ a[i]);return ans;}ll qmin(){if(f) return 0;for(int i = 0; i <= 60; ++i) if(a[i]) return a[i];return INF;}void rebuild(){for(int i = 0; i <= 60; ++i){for(int j = i - 1; j >= 0; --j) if(a[i] & (1ll << j))a[i] ^= a[j];if(a[i]) tmp[cnt++] = a[i];}}ll qry(ll k){if(f) --k;if(!k) return 0;if(k >= (1ll << cnt)) return -1;ll ans = 0;for(int i = 0; i < cnt; ++i) if(k & (1ll << i))ans ^= tmp[i];return ans;}void work(){cin >> n >> m;for(int i = 1; i <= n; ++i){ll x;cin >> x;Insert(x);}rebuild();ll l = 1, r = (1ll << cnt);while(l < r){ll mid = l + r >> 1;if(qry(mid) > m) r = mid;else l = mid + 1;}cout << (1ll << cnt) - l + f << endl;}int main(){ios::sync_with_stdio(0);//int TT;cin>>TT;while(TT--)work();return 0;}