航电提高课（线性基）2021.07.08

一、异或运算
异或运算的性质：
1、c=a^b,那么a^c=b,b^c=a。
2、a=a^b,b=a^b,a=a^b;相当于整数a,b的交换

第一题解：因为两个相同的数异或为0，只需要将2n+1个数全部异或一遍就可以得到单独的数。
第二题解：我们将前n个数异或一边，再将结果与前n+1个数异或，得到的数就是重复出现的数（不重复出现的数被异或了两次为0，重复出现的被异或了三次，得到的数就是这个数的本身）
第三题解：先将前2n+2个数异或一遍,在将结果以二进制的形式从最低为最高位去第一个为1的位置，将2n+2个数按照二进制位置的1和0分为两组，这两组会将两个不成对的数分到两个组中，最后再将两个组分别异或，得到的两个值就是2个不成对的数。

二、线性基
定义：对于一个数集A，它的线性基是一个最小的数集B，使得A中任意一个数可以通过B中的一些数的异或得到(每一个数集都至少有一个数集）。
对于一个数集，可能不止存在一个线性基，且这些线性基都是等价的。
作用：在某些涉及异或操作时，线性基可以代替原来数集，从而达到减小数据规模的目的。

求线性基：
如果X=a1^a2...^an，则意味着X可以被其他已经选择的数表示，所以就去掉X（不把X当作线性基的元素）
线性基的最高位要不同，便于计算X是否能被现有的数表示。
求线性基的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[10];//数集A 
ll d[100];//d[i]表示非0最高位，从右低位数第i位的数
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    for(ll i=1;i<=n;i++){
        ll x=a[i];
        for(int j=62;j>=0;j--){
            if(x&(1ll<<j)){
                if(d[j]==0){
                    d[j]=x;//当d[j]中有一位没有被确定时，将X存入d[j]中 
                    break;
                }
                else x=x^d[j];//将二进制中与d[j]二进制中相同位置都为1置为0 
            }
        }
    }
    return 0;
} 

线性基的三个性质：
1、线性基中没有为0的元素
2、线性基中任何一个元素都无法通过线性基中元素异或得到
3、原集合中任何一个数都可以通过线性基中的某些数异或得到

三、给出N个数a1,a2...an，能否去一些数进行异或操作得到Q
先求出这N个数的线性基，将Q经过线性基后，如果Q为0则表示可以，否则表示不可以。

bool check(ll x){
    for(int j=62;j>=0;j--){
        if(x&(1<<j)){
            if(d[j]==0){
                return false;
            }
            else x=x^d[j];
        }
    }
    if(x==0) return true;
    return false;
} 

三个常见的线性基问题
例1、求异或最大值
给出N个数，取其中一些数进行异或操作，能够得到的最大值是多少。
解：先求N个数线性基，将答案初始化为0，从高位到地位查询，若当前答案该位为0且d[j]！=0，则将当前答案异或d[j]。最后所有位都查询后的答案最是最大值。

ll maxx(){
    ll ans=0;
    for(int i=62;i>=0;i--){
        if(ans^d[i]>ans) ans^=d[i];
    }
    return ans;
} 

例2、求异或的最小值
给出N个数，取其中一些数进行异或操作，能够得到的最小值是多少。
在构造线性基的过程中，若原数集中的一个数不能插入线性中（即这个数可以被线性中的数表示，那么两个数相同异或就为0），若答案不为0，则从低位往高位看，如果一个位置d[i]不为0，则答案就是该d[i]。

例3、求异或第K小值
首先要求出N个数的线性基并化为最简单的形式，观察d[],我们只能在d[i]！=0时自由选择第i位是0还是1。由于线性基异或不会出现0，特判原数集A中异或是否会出现为0的情况，若出现则K=K-1。对于能选择的位，我们可以选择0或1，我们将K用二进制表示，若一位为0，则将可选择为选为0，否则选择1，最后就能求出异或第K小的值了。

将线性基化简位1xxxx0xxx0x的形式
1xxx0x
1x
化简后的线性基和原线性基等价，如果不化简会出错

void work(){//线性基化简函数 
    for(int i=1;i<=62;i++){
        for(int j=1;j<=i;j++){
            if(d[i]&(1<<(j-1))){
                d[i]=d[i]^d[j-1];
            }
        }
    }
}
//求第K小的值的函数 
ll kth(ll k){
    if(k==1&&lenx<len) return 0;//lenx位线性基的长度，len为原数集的长度
    //如果求最小值且原数集异或可以为0，那么最返回为0 
    if(lenx<len) k--;// 原数集异或可以为0，求第K-1小 
    work();
    ll ans=0;
    for(int i=0;i<=62;i++){
        if(d[i]!=0){
            if(k%2==1) ans^=d[i];
            k=k/2;
        }
    }
    return ans;
}

线性基例题