线性基 | 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}.
1
于是,我们把这四个数写成矩阵,就成了矩阵A.
2
.我们考虑把这个变成上三角形,那么可以r3-r2+r4,然后r3和r4互换.
就可以得到一个行阶梯型的矩阵.
于是集合{x}->{k}={1,2,10,17}.嗯,没错,{k}就是我们要求得的线性基.当然,我们也可以处理掉10,保留9
3
如果计算一下的话,会发现,得到的值域{y}是相同的.于是,我们就可以称{k}为线性基.

求解线性筛

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

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

1
2
3
4
5
6
7
8
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}$

解析

模板题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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$之间的大小关系就好了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}

 


 


 



 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载