学习线性基
我们在处理异或问题的时候可能会遇到某些恶心的问题,比如:
1.给定一个集合,可以让任意多个数异或,求最大/小异或和
2. 给定一个集合,可以让任意多个数异或,求第k小异或和
3. 给定一个集合,可以让任意多个数异或,求x能否被异或出来
这些问题我们可以使用线性基来解决。
何为线性基
线性基是一个集合,它的大小是log2原集合的值域,它的定义是
1.线性基中集合的数任意个数异或出来的值域集合与原数集合 完 全 一 致(除了没有0
2.线性基中任意个数异或出来都不会为0
其中设线性基有log2原集合的值域个数字,那么pi为最高位1在i位上的那个数字(取唯一)
那让我们来构造线性基吧
void insert(long long x)
{
for (int i=50;i>=0;i--)
{
if (!(x>>i&1)) continue;//如果第i位是1才做
if (!p[i]) {p[i]=x;break;}//如果未被占用则占用
x^=p[i];//否则去掉当前这一位1,并且保证性质1.
}
}
很短对吧,那让我们看看上面说的3个问题
实际问题
给定一个集合,可以让任意多个数异或,求最大/小异或和
最大值的话只要构造线性基然后从高位到低位如果当前这一位pi异或了以后能让ans变大就异或,因为异或高位大才是王道
#include<bits/stdc++.h>
using namespace std;
long long n,p[55];
void insert(long long x)
{
for (int i=50;i>=0;i--)
{
if (!(x>>i&1)) continue;
if (!p[i]) {p[i]=x;break;}
x^=p[i];
}
}
int main()
{
scanf("%lld",&n);
for (long long a,i=1;i<=n;i++)
{
scanf("%lld",&a);
insert(a);
}
long long ans=0;
for (int i=50;i>=0;i--)
{
if ((ans^p[i])>ans) ans^=p[i];
}
cout<<ans<<endl;
return 0;
}
最小值,只需要从低位向高位判断如果pi!=0直接输出pi即可,注意判断可不可以异或出0,这一点你们看了第三个问题或者第二个就会明白了,代码自己写写吧,我没写。
给定一个集合,可以让任意多个数异或,求第k小异或和
需要改造一下线性基,目的是让第i位为1的元素 (即pi) 在线性基中只有他的第i位为1。 处理完后再把p数组的元素从小到大依次放进p2数组,因为最高位固定,所以直接循环放 。然后神奇的规律来了:求第k小时,只要把k二进制拆分,第i位是1就异或 b[i] ,这我也不知道什么规律,反正很好记。(貌似是因为最小数依次是p0,p1,p0^p1,p2,p2^p0,p2^p1,p2^p0^p1)这里就要有异或为0的问题了,就是0是否可以做最小值。
#include<bits/stdc++.h>
using namespace std;
long long a,dp[200],dp1[200],cnt=0,n,m,f=0;
void insert(long long x)
{
for(int i=62;i>=0;i--)
{
if(x>>i&1)
{
if(!dp[i]){dp[i]=x;return;}
x^=dp[i];
}
}
f=1;//如果x还是没有找到空的pi,那x一定被异或成0了,说明x可以被之前的数异或出来,那么最小值就可以为0
}
void change()
{
for(int i=0;i<=62;i++)
{
for(int j=i-1;j>=0;j--) if(dp[i]>>j&1) dp[i]^=dp[j];//保证只有pi的i位有1且满足性质1
if(dp[i]) dp1[cnt++]=dp[i];
}
}
long long kth_min(long long k)
{
long long ans=0;
for(int i=0;i<cnt;i++) if(k>>i&1) ans^=dp1[i];
return ans;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a),insert(a);
change();//处理
unsigned long long tot=1LL<<cnt;//因为sigma i=[1,cnt] C(i,cnt)=2^cnt也就是异或的所有不同的(请注意不是n是cnt了)取值
scanf("%lld",&m);
for (int i=1;i<=m;i++)
{
long long k;
scanf("%lld",&k);
k-=f;如果能取0,那么所有排名下降一位
if(tot<=k) cout<<"-1"<<endl;//如果k比全部不同取值还大就不可能
else cout<<kth_min(k)<<endl;
}
return 0;
}
给定一个集合,可以让任意多个数异或,求x能否被异或出来
其实我2,3难度放反了说。。。
问题不大,相信大家看了2都知道怎么做了
bool insert(long long x)
{
for(int i=62;i>=0;i--)
{
if(x>>i&1)
{
if(!dp[i]){dp[i]=x;return 0;}
x^=dp[i];
}
}
return 1;//如果x还是没有找到空的pi,那x一定被异或成0了,说明x可以被之前的数异或出来
}
例题明天更(现在0:13哦)
%%%写的太好了
还没看就评论的屑
%%%写的太好了
Orz