XCPC Notes

Appearance

发布时间：2024-07-31

线性基 ​

概念 ​

线性基是针对某个序列生成的一个集合，它具有以下两条性质：

  1. 线性基中任意选择一些数的异或值所构成的集合，等于原序列中任意选择一些数的异或值所构成的集合。

  2. 线性基是满足上述条件的最小集合。

  3. 原序列中任何数，都可以由线性基中一些数异或起来得到（由性质1直接得出）

  4. 线性基中不存在一组数，使得它们的异或值为0，如果存在x xor y xor z=0则等价于x xor y =z使得异或集合变，违背了性质2）

  5. 线性基中不存在两组取值集合，使得它们的异或和相等（不然你把这两个集合异或在一起就会得到异或和为0的集合）

  6. 线性基中的数最高位数字1不重复

  7. 线性基个数小于等于原数个数

cpp
struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=60;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
    void rebuild(){
        nums.clear();
        for(int i=0;i<SIZE;i++){
            for(int j=0;j<i;j++){
                if(d[i]>>j&1)d[i]^=d[j];
            }
            if(d[i])nums.push_back(d[i]);
        }
    }
    int kth(int k,int n){
        if(nums.size()<n){
            if(k==1)return 0;
            k--;
        }
        if(k>=(1ll<<nums.size()))return -1;
        int res=0;
        for(int i=SIZE-1;i>=0;i--){
            if(k>>i&1)res^=nums[i];
        }
        return res;
    }
    int find_rank(int x){
        int rk=0,tp=1,y=x;
        for(int i=0;i<SIZE;i++){
            if(!(y>>i&1))continue;
            if(d[i])y^=d[i];
            else return -1;
        }
        for(int i=0;i<SIZE;i++){
            if(d[i]){
                if(x>>i&1)rk+=tp;
                tp<<=1;
            }
        }
        return rk;
    }
    LinearBasis operator|(const LinearBasis &rhs)const{
        LinearBasis res=*this;
        for(int i=0;i<SIZE;i++){
            if(rhs.d[i])res.insert(rhs.d[i]);
        }
        return res;
    }
    LinearBasis operator&(const LinearBasis &rhs)const{
        LinearBasis res;
        auto d=*this,all=*this;
        for(int i=0;i<SIZE;i++){
            if(!rhs.d[i])continue;
            int k=0,j;
            int v=rhs.d[i];
            for(j=i;j>=0;j--){
                if(v>>j&1){
                    if(all.d[j])v^=all.d[j],k^=d.d[j];
                    else break;
                }
            }
            if(!v)res.d[i]=k;
            else all.d[j]=v,d.d[j]=k;
        }
        return res;
    }
};

贪心构造 ​

cpp
int d[60];
void insert(int x){
    for(int i=55;i>=0;i--){
        if(!(x>>i&1))continue;
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}
//查询异或最大值
int query(){
    int res=0;
    for(int i=55;i>=0;i--){
        if(res>>i&1)continue;
        res^=d[i];
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        insert(x);
    }
    cout<<query()<<"\n";
}

高斯消元法构造 ​

cpp
int d[70];
void gauss(int n){
    int k=1;
    for(int i=62;i>=0;i--){
        for(int j=k;j<=n;j++){
            if(d[j]>>i&1){
                swap(d[j],d[k]);
                break;
            }
        }
        if(!(d[k]>>i&1))continue;
        for(int j=1;j<=n;j++){
            if(j!=k&&(d[j]>>i&1))d[j]^=d[k];
        }
        if(k==n)break;
        k++;
    }
}
void insert(int x){
    for(int i=55;i>=0;i--){
        if(!(x>>i&1))continue;
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}
int query(){
    int res=0;
    for(int i=55;i>=0;i--){
        res^=d[i];
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>d[i];
    gauss(n);
    cout<<query()<<"\n";
}

求min异或值 ​

  • 当某次数插入失败时，异或值为0
  • 否则为min d[i]

求第k小异或和 ​

  • 重构线性基，使得每一位在线性基中只有当前位为1
  • 求第k小直接对k二进制拆分算异或即可
  • 注意：如果d[i]不为0的个数小于n，说明有插入失败，存在异或为0，询问需要减一
cpp
int d[70];
void insert(int x){
    for(int i=55;i>=0;i--){
        if(!(x>>i&1))continue;
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}
vector<int> nums;
void rebuild(){
    for(int i=0;i<=55;i++){
        for(int j=i-1;j>=0;j--){
            if(d[i]&(1ll<<j))d[i]^=d[j];
        }
        if(d[i])nums.push_back(d[i]);
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        insert(x);
    }
    rebuild();
    int m;
    cin>>m;
    while(m--){
        int x;
        cin>>x;
        if(nums.size()<n)x--;
        if(x>=(1ll<<nums.size()))cout<<"-1\n";
        else{
            int ans=0;
            for(int i=55;i>=0;i--){
                if(x>>i&1)ans^=nums[i];
            }
            cout<<ans<<"\n";
        }
    }
}

求异或路径（最大值最小值） ​

  • 建立dfs树，把所有的环异或值加进线性基
  • 查询与disndis_n异或的最大值（最小值）

实数线性基 ​

cpp
const double eps=1e-6;
template <typename T>
struct Vector{
    vector<T> a;
    Vector(int n):a(n){}
    T& operator[](int i){
        return a[i];
    }
    const T& operator[](int i)const{
        return a[i];
    }
    Vector operator-(const Vector &b){
        Vector res(a.size());
        for(int i=0;i<a.size();i++)res[i]=a[i]-b[i];
        return res;
    }
    Vector operator*(const T &x){
        Vector res(a.size());
        for(int i=0;i<a.size();i++)res[i]=a[i]*x;
        return res;
    }
    Vector operator/(const T &x){
        Vector res(a.size());
        for(int i=0;i<a.size();i++)res[i]=a[i]/x;
        return res;
    }
};
template <typename T>
struct LinearBasis{
    vector<Vector<T>> d;
    int n;
    LinearBasis(){}
    LinearBasis(int n){
        init(n);
    }
    void init(int n){
        d.assign(n,Vector<T>(n));
        this->n=n;
    }
    bool insert(Vector<T> x){
        for(int i=n-1;i>=0;i--){
            if(fabs(x[i])<eps)continue;
            if(fabs(d[i][i])<eps){
                d[i]=x;
                return true;
            }
            x=x-d[i]*(x[i]/d[i][i]);
        }
        return false;
    }
};

Wenwei Lin · 2022 — 2025