「线性基」学习小结

2024-04-11 19:14:43

向量空间

向量空间亦称线性空间。

形式化的，我们定义一个向量空间\((P,V,+,\cdot)\)

其中 \(P\)是一个域，\(V\)是一个非空的集合，其中的集合称作向量，同时定义两种运算分别为向量加法和标量乘法

一个\(P\)上的向量空间\((P,V,+,\cdot)\)，需满足以下8条公理（其中的\(u,v,w\in V\),\(a,b\)是标量）：

\(u+(v+w)=(u+v)+w\)

\(u+v=v+u\)

\(\exists\mathbf{0}\)，\(s.t. \ \ v+\mathbf{0}=v\)

\(\forall v\in V,\exists w\in V\)，\(s.t.\) \(v + w = 0\)

\(a(u+v)=au+av\)

\((a+b)v=av+bv\)

\(a(bv)=(ab) v\)

\(\exists 1,s.t. \ 1 \cdot v=v\)

基（basis）

向量空间\(V\)的基是可以张成\(V\)的一个线性无关的向量组，其中的元素称作基向量。

异或运算&线性基

把一个数的二进制表示看成是一个向量
\[ \mathbf{a}_i=(d_n,...d_0) \]
假设向量\(\mathbf{a}_0,\mathbf{a}_1,...\mathbf{a}_m\)，的张成空间是\(S\)

定义一个向量空间\(V=(\{ 0,1\} ,S,xor,\cdot)\)

\(ps:\)这里，我们是把异或当作加法

求法

如何求出\(V\)的一个基\(\mathfrak{B}\)？

我们要做的：是扫描每一个向量\(\mathbf{a}_i\)，如果它存在于其它向量的张成空间中，就把它去掉

如何判断每个向量能否被前面的向量张成得到？

我们利用高斯消元:

int a[MN],base[log_MN];
inline void calc()
{
    //n is the highest bit
    register int i,j,k;
    for(i=0;i<=m;++i)for(j=n;~j;--j)
        if(a[i]>>j&1)//Scan every bit of a[I] from top to bottom
        {
            if(base[j]) a[i]^=base[j];
            else
            {
                //There's no vector for this bit
                base[j]=a[i];
                /*Maintain a diagonal matrix
                for(k=j-1;~k;--k) 
                    if(base[k]&&(base[j]>>k&1)) base[j]^=base[k];
                for(k=j+1;k<=n;++k) 
                    if(base[k]>>j&1) base[k]^=base[j];
                */
                break;
            }
        }
}

复杂度是\(O(mn)\)，若位数较多，通常采用bitset优化，复杂度是\(O(\frac{mn^2}{\omega})\)

可以发现，我们在维护一组向量\(base[]\)，满足\(base_i\)的最高位时\(i\)

为了方便，通常只把它消成一个上三角矩阵

当然，你也可以把它消成一个类对角线矩阵，满足每一位最多只存在于一个向量中

线性基的运用

在这里，我们不严谨地称一个向量<另一个向量

其实指的是，每个向量对应的数的大小比较

查询最值

贪心求最大值：

如果所求是类对角线矩阵，直接将所有向量相加即可

如果所求的是上三角矩阵，从高到低遍历每个向量，若ans加上当前的向量会变大，就将其贪心的加上

最小值是线性基中最小的向量

查询第k小值

首先在去重的前提下。

首先我们求出类对角线矩阵

那么，如果 \(k=(100101)_2\)，我们所求的即为\(base_0 +base_2+base_5\)

也就是各位所对应的数Xor起来即可

查询和是第几大

如果在去重的前提下，和查询第k小差不多。

如果不在去重的前提下的话：

设\(m\)为给出数的个数， \(\mathfrak{B}\)为所求线性基

结论：每个数都出现一样的次数，且这个次数为 \(2^{m - \vert \mathfrak{B}\vert}\)

证明：

所有不在线性基中的数的个数为 \(m - \vert \mathfrak{B}\vert\)，我们任意选择它的一个子集 \(S\)，对于 \(S\) 中的每个数 \(v\)，有唯一的方式表达为 \(\mathfrak {B}\)中向量的线性组合。我们对于每个 \(v\)，将这个线性组合中的向量都选上（一个向量选多次可以看作是次数对\(2\)取模后的结果），两个相同的数异或起来得到 \(0\)，所以对于每个数 \(x\)，我们都能找到至少\(2^{n - \vert \mathfrak{B}\vert}\) 种不同的选择方案，使得异或值为 \(x\)。又因为对于每个子集 \(S\)，为了使得最终异或值为 \(x\)，选择线性基中的向量的方案是唯一的，所以上界也是 \(2^{n - \vert \mathfrak{B}\vert}\)。

（此结论同时出现在2019/2/24 福建四校联考中的T1）

总结

观察大佬博客Sengxian'blog后......

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

最大异或和（例题：luogu模板题）

第 \(k\)大异或和/异或和是第几大（例题：bzoj 2844）

求所有异或值的和（例题：bzoj 3811）

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

任意一条\(1\) 到 \(n\) 的路径的异或和，都可以由任意一条 \(1\)到 \(n\) 路径的异或和与图中的一些环的异或和来组合得到。（例题：bzoj 2115）

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

Code

暂时咕咕咕。

Blog来自PaperCloud，未经允许，请勿转载，TKS！

码农公寓