学习线性基

我们在处理异或问题的时候可能会遇到某些恶心的问题，比如：

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哦)