牛牛数数 【线性基+二分】

本文主要是介绍牛牛数数 【线性基+二分】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/10845/E
来源：牛客网

保证答案在long long内。

解法

这题可以说是线性基的模板题。先学习一下线性基：
线性基视频
处理完线性基之后，就可以使用其性质4：

1. 求任意子集xor最大值: 把线性基中所有元素xor起来
2. 求任意子集xor最小值: 等于最小的主元
3. 查询x是否在值域中: 如果x能插入线性基，则x不能被当前线性基xor出来
4. 查询第k小的值: 把k进行二进制分解，把1对应位置的主元xor起来；注意这里第0小就是0
5. 求任意子集与x进行xor的最大值：从高->低贪心，若xor上a[j]能变大就xor

然后进行二分，二分到第一个大于k的数在线性空间中能排第几。如果线性基中有n个主元，那么一共有$2^n$种不同数在线性空间中。然后答案就是$最后一个排名(2^n-1)-第一个大于k的排名+1$。

代码

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>
#include <cmath>
#include <set>#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;template<class T>void read(T &x){T s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {read(h);read(t...);
}void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}//--------------------------------------------int N,L = 62;
ll K;
ll a[maxn];
int zero = 0;
bool insert(ll x){ //线性基插入模板for(int j = L;j>=0;j--){if((x>>j & 1LL) == 0) continue;if(a[j]){x ^= a[j];continue;}for(int k = j - 1;k>=0;k--){if((x>>k & 1LL)){x ^= a[k];}}for(int k = L;k>j;k--){if((a[k]>>j & 1LL)){a[k] ^= x;}}a[j] = x;return 1;}return 0;
}
ll judge(ll mid){ll ans = 0;int tag = 1;for(int j = 0;j<=L;j++){if(a[j] == 0) continue;if(mid & 1LL){ans ^= a[j];}mid/=2;}return ans;
}
void solve(int cnt){ll total = 1LL<<cnt;ll l = 0,r = (1LL<<cnt)-1,ans = total+1;while(l<=r){ll mid = (l+r)>>1;if(judge(mid) > K) {r = mid-1,ans = mid;}else l = mid+1;}if(ans >= total) puts("0");else{printf("%lld\n",total-1 - ans + 1);}}int main() {
//    debug_in;
//    debug_out;read(N,K);int cnt = 0;go(i,1,N) {ll x;read(x);if(insert(x)) cnt++;}solve(cnt);return 0;
}

这篇关于牛牛数数 【线性基+二分】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---