CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 线性基 ======

===== 定义 =====

对于一组数 $a_1,a_2,...,a_n$ ，他们的线性基为 $p_1,p_2,...,p_m$ ，其中 $p_i$ 是指出现1的最高位在第 $i$ 位上的那个数。

===== 构造方法 =====

对于每个数，我们先找出他的最高位的1在第 $i$ 位，假如 $p_i$ 此时为零，那么将这个数假如线性基，否则异或 $p_i$ 继续找。

===== 应用 =====

==== 求一组数中若干个数异或值的最大值 ====

根据线性基的性质，直接将线性基中的所有数异或起来即可

==== 求一组数中若干个数异或的第 k 小 ====

将 $k$ 分解为二进制，第 $2^i$ 位对应线性基中从低到高的第 $i-1$ 个非空位，若是1则将答案异或上线性基中这一位的数

==== 询问一个数在一堆数中的任意异或值排第几（算上重复） ====

一堆数取若干个数的异或值，每种异或值出现的次数都是相等的，$2xor(n-|B|)$

===== 例题 =====

[[https://www.luogu.com.cn/problem/P3812|洛谷p3812]]

<code cpp>
#include<bits/stdc++.h>
#define reg register
using namespace std;
typedef long long ll;
const int MN=60;
ll a[61],tmp[61];
bool flag;
void ins(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
    flag=true;
}
bool check(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i])return false;
            else x^=a[i];
    return true;
}
ll qmax(ll res=0){
    for(reg int i=MN;~i;i--)
        res=max(res,res^a[i]);
    return res;
}
ll qmin(){
    if(flag)return 0;
    for(reg int i=0;i<=MN;i++)
        if(a[i])return a[i];
}
ll query(ll k){
    reg ll res=0;reg int cnt=0;
    k-=flag;if(!k)return 0;
    for(reg int i=0;i<=MN;i++){
        for(int j=i-1;~j;j--)
            if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1ll<<cnt))return -1;
    for(reg int i=0;i<cnt;i++)
        if(k&(1ll<<i))res^=tmp[i];
    return res;
}
int main(){
    int n;ll x;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&x),ins(x);
    printf("%lld\n",qmax());
    return 0;
}
</code>
CVBB ACM Team

用户工具

站点工具

页面工具
