线性基

JK_LOVER · 2020-04-29 17:24:30 · 题解

若格式炸了来这里博客

线性基

介绍：

用一个权值大小为 [1,\log n] 的数组来表述一个权值大小为 [1,n] 的原数组的异或问题的数据结构。

实质：

多维向量的作为基底的特殊形式，可用高斯消元理解。（关于实质下文用题专门讲解）

性质：

1.线性基是原数组的极大线性无关组。所以线性基也就拥有一下性质：
（1）只含零向量的向量组没有极大无关组；
（2）一个线性无关向量组的极大无关组就是其本身；
（3）极大线性无关组对于每个向量组来说并不唯一，但是每个向量组的极大线性无关组都含有相同个数的向量；
（4）齐次方程组的解向量的极大无关组为基础解系。
（5）任意一个极大线性无关组都与向量组本身等价。
（6）一向量组的任意两个极大线性无关组都是等价的。
（7）若一个向量组中的每个向量都能用另一个向量组中的向量线性表出，则前者极大线性无关向量组的向量个数小于或等于后者。----来自于百度
2.线性基中每个元素只有唯一异或方案。
3.线性基的每一个的元素的最高位也是该元素在线性基的位次。（此性质是定义）。
4.线性基的二进制最高位互不相同。（此性质是定义）
5.如果线性基有 n 个元素，它的可异或的个数为 2^n-1。
6.线性基中元素互相异或，异或集合不变。

证明：

性质1：线性基中每个元素只有唯一异或方案：

A,B,C,D四个不可被相互表达的元素，但 \oplus 满足交换率。所以总有一个元素是多余的。

A \oplus B = C \oplus D \Leftrightarrow A \oplus B \oplus C = D

性质2：线性基有 n 个元素，它的可异或的个数为 2^n-1：

因为 \oplus 有性质 A\oplus A=0 所以，在表示的元素中，要么这个元素参与组成，要么不参加组成。而又因为性质1，所以一个原元素可表达为：

A=a_1 b_1\oplus a_2 b_2 \oplus....\oplus a_nb_n (a_i=1,0)

而又因为 a_i 不可全为 0 所以共有 2^n-1 个元素可被表达。

性质3：线性基中元素互相异或，异或集合不变：

仍可用异或的交换率来解释，本人感觉这条和性质2是等价的。

运用：

终于到了正题,我们先来了解一下线性基的构建。

构建线性基

因为线性基要满足 \text{线性基的二进制最高位互不相同} 这条性质的，所以我们在建造线性基就必须注意这一点。

在每次插入一个数时由高到低枚举二进制位，当这个元素此位是一时，若此位已经被插入就用它异或该位的元素，这样是为了满足 \text{线性基的每一个的元素的最高位也是该元素在线性基的位次} 这个性质。

否则就将该元素放入，然后退出。

void insert(int x)//插入线性基 
{
    for(int i = 63;i>=0;i--)
    {
        if(x&(1LL<<i))
        {
            if(!p[i])
            {
                p[i]=x;
                return;
            }
            x^=p[i];
        }
    }
}

查询异或最大值

当我们已经构建完线性基之后，我们就可以利用性质来实现一些算法了。

考虑最大异或最大值一定是尽量让最高位为1的元素，就可以考虑以下贪心：由高到低枚举线性基中的元素，如果此位为0，那么异或后一定更优，如果为1，那么异或后一定不会更优。

    for(LL i = 62;i >= 0;i--)
    {
        if((ans>>i)&1)continue;
        else 
        ans^=p[i]; 
    }

或者直接这样写

for(LL i = 62;i >= 0;i--)
    {
        if((p[i]^ans)>ans)
        {
            ans^=p[i];
        }
    }

都是可以的。

查询异或最小值

考虑最大异或最小值一定是尽量让最高位为0的元素，这不就是线性基最低位的性质嘛，那就直接输出最小值就好了。这就错了，我们在下定义时是将 0 这个值排除的。所以还要特判是否有一个元素是没有被插入的

int Min()//最小 
{ 
    if(pd==1) return 0;//如果可以构造出0，这里需要特判 
    for(int i = 0;i <= 62;i++)
    if(p[i]) return p[i];
}

查询第k大值

这里要用以下性质：

如果线性基有 n 个元素，它的可异或的个数为 2^n-1。
线性基中元素互相异或，异或集合不变。
（6）一向量组的任意两个极大线性无关组都是等价的。（等同于上面一条）

为了实现更多的功能，我们必须对原线性基改造。

rebuild

经过这个函数，我们可以使线性基有一个非常优秀的性质：

一个数二进制拆分后，每一位的线性基异或后所得到的值严格大于一个比它小的数所得的值。
```
void rebuild()//重构线性基 
{
for(int i = 63;i >= 0;i--)
for(int j = i-1;j >= 0;j--)
if(p[i]&(1LL<<j)) p[i]^=p[j];
for(int i = 0;i <= 63;i++) if(p[i]) d[cnt++]=p[i];
}
```
作用显然是把一个高位的线性基的其它位变得更小，那又有什么用呢？我们考虑用证明：我们可以证明一个首项为 1 公比为 2 的等比数列是满足：

a_i+a_j \neq a_i + a_k (k\neq j)

a_i+a_j \neq a_k + a_l

上式满足 i 和 j 不同时等于 k 和 l 。

从而可得 n 个数可构造 2^{n} 个不同的数，而线性基则可看作为一种缺少某一项的等比数列之和。

又因为一个 n-1 位的数无论怎么异或都不能大于或等于 2^n 。所以有第 n 个线性基参与的数一定在其下有 2^{n-1}-1 个数。而第 m 是没有线性基的，所以只能往上增加 2^{n-1} 个。

第k大值

有了这个性质我们就可以轻易的写出查询第 k 大的代码了。当然如果都大于线性基的个数范围了就可以 return 掉。

int kth(int k)//第k大 
{
    if(k >= (1LL<<cnt)) return -1;
    int ans=0;
    for(int i = 62;i>=0;i--)
    {
        if((k>>i)&1) ans^=d[i];
    }
    return ans;
}

例题（代码）

P3812 【模板】线性基模板题，正常思路即可。

```cpp #include<bits/stdc++.h> using namespace std; #define int long long int read() { int x=0,f=0;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return f?-x:x; } #define N 100 int p[N],n,m,d[N],cnt=0; void rebuild()//重构线性基 { for(int i = 63;i >= 0;i--) for(int j = i-1;j >= 0;j--) if(p[i]&(1LL<<j)) p[i]^=p[j]; for(int i = 0;i <= 63;i++) if(p[i]) d[cnt++]=p[i]; } void insert(int x)//插入线性基 { for(int i = 63;i>=0;i--) { if(x&(1LL<<i)) { if(!p[i]) { p[i]=x; return; } x^=p[i]; } } } int kth(int k)//第k大 { if(k >= (1LL<<cnt)) return -1; int ans=0; for(int i = 62;i>=0;i--) { if((k>>i)&1) ans^=d[i]; } return ans; } int Max()//最大 { return kth((1LL<<cnt)-1); } signed main() { n=read(); for(int i = 1;i <= n;i++){insert(read());} rebuild(); cout<<Max()<<endl; return 0; } ``` $II

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
LL read()
{
    LL x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
LL n,ans,p[1919191];
void work(LL x)
{
    for(LL i = 62;i >= 0;i--)
    {
        if((1LL<<i)&x) 
        {
            if(!p[i]) {
                p[i] =x;
                return ;
            }
            x^=p[i];
        }

    }
}
int main()
{
    n=read();
    while(n--)
    work(read());
    for(LL i = 62;i >= 0;i--)
    {
        if((ans>>i)&1)continue;
        else 
        ans^=p[i]; 
    }
    cout<<ans<<endl;
}