线性基学习笔记

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

线性基学习笔记

作者：

检控方没有异议 , 2022-02-10 14:33:12 , 所有人可见 , 阅读 227

我讲不懂这玩意，都是一些自己的理解和表述，如果有错希望您能不吝赐教。

学习资料

形式

异或意义下（OI常用）
向量意义下

向量意义下的是它的本质。

xor 意义下

给你一个数列，它的基底就是一堆可以通过 xor 运算，表示出这个数列里全部数的数字。

这堆数字满足：
1. 个数最少且个数唯一
2. 对于每一个数，其表示方式是唯一的，而且表示不出 $0$
3. 这堆数字是啥不是一定的

向量意义下

运算从 xor 变成向量加法和数乘。其他类比 xor 意义下。

可以用来干啥

查询异或最值
求一个数能不能异或出来
求异或 $kth$
求一个数的 $rank$

构造

一种仅适用于 xor 意义下的我也不知道叫啥的方法
高斯消元

先介绍第一种。

自己瞎分析一下原理：如果数列中任意一个数在二进制下第 $i$ 位是 $1$ ，那么线性基中第 $i$ 个数的第 $i$ 位也是 $1$ 。

否则由于表示的方案是唯一的，插入的数需要 xor 上线性基中第 $i$ 个数。

实现

//这是模板题的 insert 代码
inline void ins(ll t)
{
    if(!t) return ;
    for(int i=49;~i;i--)
        if((t >> i)&1)
        {
            if(!a[i]) {a[i]=t; return ;}
            t^=a[i];
        }
    return ;
}

第二种不是很常用，我只做过一道题P3265 [JLOI2015]装备购买题解。

题意转化：输出线性基中元素个数和线性基中元素所带来的最小代价。

每个装备如果是可以被其他装备凑出来的，可以转化为一个多元线性方程组。

贪心购买装备，并用手中的装备尝试凑出其他没拿到的装备，这个过程就是高斯消元。

实现

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

struct node
{
    double z[520];
    int c;
    bool operator <(const node &x) const {return c < x.c;}
} a[520];

int pos[520];

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    int n,m,ans=0,cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lf",&a[i].z[j]);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].c);
    sort(a+1,a+1+n);

    double div;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(fabs(a[i].z[j]) < fabs(1e-5)) continue ;//自由元
            //向基底中加入一个向量
            if(!pos[j]) {pos[j]=i; cnt++; ans+=a[i].c; break ;}
            else
            {
                div=a[i].z[j]/a[pos[j]].z[j];
                for(int k=j+1;k<=m;k++) a[i].z[k]-=div*a[pos[j]].z[k];
            }
        }
    printf("%d %d",cnt,ans);
//  fclose(stdin); fclose(stdout);
    return 0;
}

求异或最值

从高位往低位贪心，如果异或后能使答案变大则异或。

inline ll querymax()
{
    ll res=0;
    for(int i=50;~i;i--)
        if((res^a[i]) > res) res^=a[i];
    return res;
}

求一个数能不能异或出来

尝试插入线性基，能插入说明不行。

inline bool check(int x)
{
    if(!x) return true;
    for(int i=20;~i;i--)
        if((x>>i)&1)
        {
            if(!a[i]) return false;
            x^=a[i];
        }
    return true;
}

求异或 $kth$

Acwing210. 异或运算

需要对线性基进行处理，把每一个元素变成满足线性基性质，同时还要最小。

这样可以保证我们对 $k$ 二进制拆分的异或结果是正确的。

注意如果原序列能异或出 $0$ 的话，$k$ 要减去 $1$ ，因为线性基是 $xor$ 不出 $0$ 的。

打卡代码

求一个数 $rank$

长得特别像上一个反过来。

inline int qry(int t)
{
    for(int i=0;i<=30;i++)
        if(a[i]) d[tot++]=i;
    int res=0;
    for(int i=0;i<tot;i++)
        if((t >> d[i])&1)
            res|=1<<i;
    return res%mod;
}

口胡原理:如果这一位是 $1$ ,一定是 $xor$ 了线性基中第 $i$ 个元素。所以加上 $2^i$ 。