线性基 | Kyons'Blog

定义

~~即使线性代数课结束,依然逃不过线性代数~~
线性基,类似于线代里面的矩阵求最大线性无关组.
看一下大佬的说法:锵锵,传送门%%%%

首先来看一个问题：给出N个数,要从中选出一个最大的子集,使得子集中的任意个元素异或值不为0.
这个和极大线性无关组有些类似。异或可以看出是模2域下的加法运算,如果把一个数转化为二进制,对应成一个由01构成的向量,
所有这些向量就构成了一个线性空间。原问题就转化为求这个向量组的极大线性无关组,把这样一个极大线性无关组成为线性基。
可以用$O(60*60*n)$的高斯消元来解决。但是还有更加快速的构造线性基的方法：复杂度是$O(60*n)$

思想

可以这么看,我们有n多个数.这些数x相互xor(异或)得到的一些数y,我们称y是他们x的值域.但是n多个数可能都太大,不好维护或者储存.于是我们想用尽量小的数,假使有k个比较小的数,相互xor同样能求出值域y.而这些k个数,我们就称之为线性基.
又有xor是在(0,1)为基底的空间里的运算.所以我们要把n多个数,解成二进制.举个栗子:
我们有集合{x}={2,9,10,17}他们相互异或可以得到值域{y}.但是这4个数,太大了~~夸张一下~~.我们就要想办法缩小x得到集合{k}.

于是,我们把这四个数写成矩阵,就成了矩阵A.

.我们考虑把这个变成上三角形,那么可以r3-r2+r4,然后r3和r4互换.
就可以得到一个行阶梯型的矩阵.
于是集合{x}->{k}={1,2,10,17}.嗯,没错,{k}就是我们要求得的线性基.~~当然,我们也可以处理掉10,保留9~~

如果计算一下的话,会发现,得到的值域{y}是相同的.于是,我们就可以称{k}为线性基.

求解线性筛

由图3,很明显我们知道了一个求线性基的方法,是高斯消元.但是太麻烦,繁琐,耗时.常用的是另一种.
一句话介绍就是:

将x转换为二进制,从高位向低位扫,如果第一个1是第p位,如果$k_p=0$,就令$k_p=x$;如果$k_p!=0$,就令$x$XOR$k_p$后,重复上述阶段.

for(int i = Bit ; i >= 0 ; i-- )   //Bit是二进制的位数,常见题目大多为62.
    if( 1 << i & Num )
        if( !Base[i] ) {
            Base[i] = Num ;
            break ;
        }
        else
            Num ^= Base[i] ;

常用操作

一.查询最值

贪心,从高位向低位贪心,可知,从高到底,后面的无法改变高位,只要高位变为最大的即可

1 2	for (int i = 62; i >= 0; i--) ans = max(ans, ans^p[i]);

二.查询最小值

贪心,从高位向低位贪心,可知,从高到底,后面的无法改变高位,只要高位变为最小的即可

1 2	for (int i = 62; i >= 0; i--) ans = min(ans, ans^p[i]);

常见题目

一.P3812 【模板】线性基

这是一道模板题。

题目描述

给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

输入输出格式

输入格式:
第一行一个数n，表示元素个数
接下来一行n个数
输出格式：
仅一行，表示答案。

输入输出样例

输入样例#1:
2
1 1
输出样例#1:
1

说明

$1≤n≤50,0≤S_i≤2^{50}$

解析

模板题目

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
using namespace std;
    
typedef long long ll;
const int maxn = 1e5 + 10;
ll a[maxn], p[maxn], dp[maxn];
int main()
{
    int n;
    ll ans=0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i <n ; i++)
        for (int j = 62; j >= 0; j--)
            if (1ll << j & a[i])
                if (!p[j]) {
                    p[j] = a[i];
                    break;
                }
                else
                    a[i] ^= p[j];
    for (int i = 62; i >= 0; i--)
        ans = max(ans, ans^p[i]);
    cout << ans << endl;
    return 0;
}

二.小a与星际探索

链接：https://ac.nowcoder.com/acm/contest/317/C
来源：牛客网

题目描述

小a正在玩一款星际探索游戏，小a需要驾驶着飞船从1号星球出发前往n号星球。其中每个星球有一个能量指数p。星球i能到达星球j当且仅当$p_i>p_j$。
同时小a的飞船还有一个耐久度t，初始时为1号点的能量指数，若小a前往星球j，那么飞船的耐久度会变为$t$⊕$p_j$(即$t$异或$p_j$，关于其定义请自行百度)
小a想知道到达n号星球时耐久度最大为多少.
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关

输入描述:

第一行一个整数n，表示星球数
接下来一行有n个整数，第i个整数表示pi

输出描述:

一个整数表示到达n号星球时最大的耐久度
若不能到达n号星球或到达时的最大耐久度为0则输出−1

示例

输入
3
457 456 23
输出
478
说明
小a有两种方法到达3号星球
第一种：1→2→3，最终耐久度为457⊕456⊕23=22
第二种：1→3，最终耐久度为457⊕23=478
输入
4
2 4 4 2
输出
-1
输入
5
234 233 123 2333 23
输出
253
备注:1⩽n,∀pi⩽3000

解析

求从$p_1$到$p_n$的异或和最大值,套板子….然后注意的是$p_i$到$p_j$的话需要$p_i>p_j$.所以不符合的数直接扔掉就可以了.
最后再判断一下$p_1$和$p_n$之间的大小关系就好了.

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn], p[maxn];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i];
    for (int i = 0; i <n ; i++)
        for (int j = 12; j >= 0; j--) 
            if (1ll << j & p[i]&&p[0]>p[i]&&p[i]>p[n])
                if (!a[j]) {
                    a[j] = p[i];
                    break;
                }
                else
                    p[i] ^= a[j];
    int ans = p[0] ^ p[n - 1];
    for (int i = 12; i >= 0; i--)
        ans = max(ans, ans^a[i]);
    cout << (p[0]>p[n-1]?ans:-1) << endl;
    return 0;
}