线性基学习笔记

layout: post
title: 线性基学习笔记
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 线性基

总结

线性基的题型相对比较固定，看到下面的类型基本上都是线性基了：

1. 最大异或和
2. 第 k 大异或和/异或和是第几大
3. 求所有异或值的和

线性基中的题目中还用到一个技巧：

• 任意一条 1到 n 的路径的异或和，都可以由任意一条 1 到 n 路径的异或和与图中的一些环的异或和来组合得到。

这便是线性基的全部东西了。

模板

struct Linear_Basis{
    long long d[65],p[65];
    int cnt;
    Linear_Basis(){
        memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));
        cnt=0;
    }

    bool ins(long long val){
        for (int i=62;i>=0;i--) {
            if (val&(1LL<<i)){
                if (!d[i]){
                    d[i]=val;
                    break;
                }
                val^=d[i];
            }
        }
        return val>0;
    }

    long long query_max(long long D=0LL){
        long long ret=D;
        for (int i=62;i>=0;i--)
            if ((ret^d[i])>ret) ret^=d[i];
        return ret;
    }

    long long query_min(long long D=0LL){
        long long ret=D;
        for(int i=0;i<=62;i++){
            if(d[i]) ret^=d[i];
        }
        return ret;
    }

    void rebuild(){
        for (int i=1;i<=62;i++)
            for (int j=0;j<i;j++)
                if (d[i]&(1LL<<j)) d[i]^=d[j];
        cnt=0;
        for (int i=0;i<=62;i++)
            if (d[i]) p[cnt++]=d[i];
    }
    //第K大
    long long kthquery(long long k){
        long long ret=0;
        if (k>=(1LL<<cnt)) return -1;
        for (int i=0;i<=62;i++)
            if (k&(1LL<<i)) ret^=p[i];
        return ret;
    }
    Linear_Basis merge(const Linear_Basis &n1,const Linear_Basis &n2){
        Linear_Basis ret=n1;
        for(int i=62;i>=0;i--)
            if(n2.d[i])ret.ins(n2.d[i]);
        return ret;
    }
};

A.BZOJ-2460 [BeiJing2011]元素

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+50;
//线性基
struct Linear_Basis{
    long long d[65],p[65];
    int cnt;
    Linear_Basis(){
        memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));
        cnt=0;
    }

    bool ins(long long val){
        for (int i=62;i>=0;i--) {
            if (val&(1LL<<i)){
                if (!d[i]){
                    d[i]=val;
                    break;
                }
                val^=d[i];
            }
        }
        return val>0;
    }

    long long query_max(long long D=0LL){
        long long ret=D;
        for (int i=62;i>=0;i--)
            if ((ret^d[i])>ret) ret^=d[i];
        return ret;
    }

    long long query_min(long long D=0LL){
        long long ret=D;
        for(int i=0;i<=62;i++){
            if(d[i]) ret^=d[i];
        }
        return ret;
    }

    void rebuild(){
        for (int i=1;i<=62;i++)
            for (int j=0;j<i;j++)
                if (d[i]&(1LL<<j)) d[i]^=d[j];
        cnt=0;
        for (int i=0;i<=62;i++)
            if (d[i]) p[cnt++]=d[i];
    }
    //第K大
    long long kthquery(long long k){
        long long ret=0;
        if (k>=(1LL<<cnt)) return -1;
        for (int i=0;i<=62;i++)
            if (k&(1LL<<i)) ret^=p[i];
        return ret;
    }
};
struct node{
    ll a,b;
    bool operator <(node a)const{
        return this->b>a.b;
    }
}my[1100];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    Linear_Basis LB=Linear_Basis();
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>my[i].a>>my[i].b;
    }
    sort(my,my+n);
    ll ans=0;
    for(int i=0;i<n;i++){
        if(LB.ins(my[i].a))ans+=my[i].b;
    }
    cout<<ans<<endl;
    return 0;
}

线性基学习笔记

原文：https://www.cnblogs.com/luowentao/p/10332305.html